COMMENT ⊗   VALID 00019 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	.Sec(Symbolic Expressions,Symbolic expressions)
C00021 00003	.SS(Symbolic Expressions: Abstract Data Structures)
C00028 00004	.<<Examples: S-exprs non S-exprs>>
C00033 00005	.SS(Trees: Representations of Symbolic expressions)
C00037 00006	.GROUP
C00041 00007	.REQUIRE "PROB1.PUB" SOURCE_FILE
C00042 00008	.SS(Primitive Functions)
C00056 00009	.<<car and cdr>>
C00063 00010	.<<discussion of components of function def>>
C00077 00011	.SS(Predicates and Conditional Expressions,conditional expression)
C00086 00012	.BEGIN "x12" CENTERIT
C00098 00013	We cannot require all our functions to be strict if we expect to do any  
C00108 00014	.FP
C00115 00015	.REQUIRE "PROB2.PUB" SOURCE_FILE
C00122 00016	.SS(Sequences: Abstract Data Structures,,P100:)
C00142 00017	.SS(Lists: Representations of Sequences,lists)
C00158 00018	.BEGIN TURN ON "←"
C00171 00019	.SS(A Respite,,P290:)
C00192 ENDMK
C⊗;
.Sec(Symbolic Expressions,Symbolic expressions)
.SS(Introduction)
.FP
This book is a study of data structures and programming languages;
in particular it is a study of data structures and programming
languages centered around the language LISP. However, this is not 
a manual to help you become a proficient LISP coder.
We will study many of the formal and theoretical aspects of languages  and
data structures as well as examining the practical applications of
data structures. We will show that this area of computer science
is a discipline of importance and beauty, worthy of careful study.
How are we to proceed? How do we introduce rigor into a field
whose countenance is as %3ad hoc%* and diverse as that of programming?
We must bear in mind that the results of our studies are to have
practical applications.
We must not pursue theory and rigor without proper
regard for practice. Our study is not that of pure mathematics; our
results will have applications in everyday programming practice.
However, for guidance let's look at mathematics. Here is a well-established discipline
rich in history and full of  results of both practical and theoretical
importance.

One of the more fertile, yet easily introduced areas of mathematics, is that of
elementary number theory. It is easy to introduce because
everyone knows something  about the natural numbers.
Number theory studies properties of a certain class of operations definable
over the set %dN%* of non-negative integers also called natural numbers.
A very formal presentation might begin with a construction of %dN%*
from more primitive notions, but it is usually assumed that the reader
is familiar with the fundamental properties of %dN%*.
In either case the next step would be to define the
class of operations which we would allow on our domain.

We shall begin our study of LISP in a similar manner, 
as an investigation of a certain
class of operations definable over  a domain of objects, called Symbolic Expressions.
Though most people
know something about the natural numbers, we are perhaps not so fortunate when it
comes to Symbolic expressions. 
We must define what we mean by "symbolic expression". 
Let's look to mathematics again
for help. If we asked someone to define the domain %dN%*⊗↓We will not attempt to
arrive at a completely self-contained definition of "natural number".
That is a difficult undertaking. See ⊗↑[Goo#57]↑. We will be
satisfied with discussing %6some%1 of their characteristics.←, the definition
we would receive 
would depend on how familar that individual was with the properties of the
natural numbers.

For most people and most purposes,  the following  characterization of a natural number
is satisfactory:

.BEGIN TABIT1(5);
.pt24
%2I%* \A natural number is a sequence of decimal digits.
.pt24
.END
.FP
The definition assumes the terminology of "sequence", "decimal" and "digit"
are known. If any of these terms are %6not%1 understood, they can be
further elaborated. However, this process of explanation and description
must terminate. We must assume that some concepts require no further
elaboration. The current definition suffers from a different kind of
inadequacy. It fails to  illuminate
the relationships between natural numbers.
The "meaning" of the natural numbers is missing. It is
like giving a person an alphabet and rules for forming syntactically
correct words but not supplying  a dictionary which relates these words to
the person's vocabulary.

If pressed for details we might attempt a more elaborate
characterization like the following:
.pt24;
.BEGIN GROUP;
.ONCE indent 5,5
%21.%* %3zero%* is an element of %dN%*.
.ONCE indent 0,5;
%2II%*###%22.%* If %3n%* is in %dN%* then  the %3successor%* of %3n%* is in %dN%*.
.ONCE indent 5,5
.SELECT 1;
%23.%* The only elements of %dN%* are those created by finitely many applications 
of rules %21%* and %22%*.
.END
.FP
Definition %2II%* appears to be completely at the other end of the spectrum;
it tells us very little about the appearance of  the integers. It gives us an
initial element %3zero%* and an operation  called %3successor%*,
which is  to exhibit a new element, given an old one.
Unless we are careful about the meaning of %3successor%*, definition %2II%*
will be  inadequate. For example if we define the
successor of a natural number to be that same number then %2II%* is satisfied
but unsatisfactory.

We can  define %3successor%* as a specific mapping, %2S%1,
which creates new elements subject to the rules that
two elements, %3x%1 and %3y%1 are equal just in the case that
%2S%3(x)%1 equals %2S%3(y)%1; and %2S%3(x)%1 is different from %3x%1, for any
element %3x%1.
We select a distinguished element, %30%*, as a
notation for %3zero%*; and   abbreviate %2S%3(0)%1, as %31%1, etc. in the
usual manner.

The characterization  of decimal digits  given in %2I%*
is syntactic.
The notation itself tells us nothing about the interrelationships between the
numbers, but it does give us a  notation for representing them.
Thus %32%* can be used to represent  %3two%* or 
used as an abbreviation for %2S%3(%2S%3(0))%1.
One benefit of the %2S%*-notation is that it explicitly shows the
means of construction. That is, it shows more of the properties of 
these numbers than just distinguishability.
We shall refer to the digit representation as %2numerals%* and reserve the
term, %2natural number%1, for the abstract object.
Thus numerals denote, stand for, or represent the abstract objects called
natural numbers; and definition %2I%1 is better stated as: "a natural number
can be represented as a finite sequence of digits".

But notation and syntax are necessary and we must be able to give precise
descriptions of syntactic notions.  
Given a choice between the two previous definitions, %2I%* and %2II%*, 
it appears that %2II%* is more precise.
Much less is left to the imagination; given
%3zero%* and a definition of %3successor%* the definition will act as a
recipe for producing elements of %dN%*. This style of definition is called an
⊗→inductive definition↔← or ⊗→generative definition↔←.

.BEGIN "x1" GROUP;
.P117:
The basic content of an inductive definition
of a set of objects consists of three parts: 
.BEGIN INDENT 10,10;
.PT24;
(1) A description of an initial set of objects; the elements of this
set are the initial elements of the set we are describing in the
inductive definition.
.END
.fp;
%2IND%*
.BEGIN indent 10,10;
(2) Given the description of some existing elements
in the set, we are given a means of constructing more elements.  
.PT2;
(3) A termination clause, saying that the only elements in the set are those
which gained admittance by either (1) or (2).
.END
.END "x1"
.PT24;
.FP
Notice that our definition of %dN%*, in terms of %3zero%* and %3successor%*,
is an instance of %2IND%*: we are defining the set of natural numbers:
%3zero%* is initially included in the set; then applying the second phrase
of the definition we can say that %3one%* is in the set since %3one%* is the
successor of  %3zero%*.

We can recast the positional notation description as an inductive definition.

.BEGIN GROUP;
.PT24;
.NL;
%21.%*##A numeral is a digit
.NL;
%22.%*##If %3n%* is a numeral then %3n%* followed by a digit is a numeral.
.NL;
%23.%1##The only numerals are those created by finitely many applications of %21%* and %22%*.
.END
.PT24;
.FP;
In words, "a numeral is a digit, or a numeral followed by a digit".

In this application of %2IND%*, the initial set has more
than one element; namely the  ten decimal digits.
Again, we assume that the questioner knows what "digit" means.
This is a characteristic of all definitions:
we must stop %6somewhere%* in our explication. 
Notice too that we assume  that "followed by" means juxtaposition.


Inductive definitions  have been the province of mathematics for
many years; however, computer science has 
developed a style of syntax specification 
called BNF (Backus-Naur Form) equations which has the same intent as
that of inductive definitions.  Here is the previous inductive definition
of "numeral" as a set of BNF equations:

.BEGIN TABIT1(15);
.BOXA
.ONCE  INDENT 0
<numeral>\::= <digit>
.PT2
<numeral>\::= <numeral><digit>
.FP
As an abbreviation, the  two BNF equations may also be written:
.ONCE INDENT 0;
<numeral>\::= <digit> | <numeral><digit>.
.BOXB
.END
.FP
A comparison between the BNF and the inductive descriptions of
"numeral"  should clarify much of the notation, but
we will give a more detailed analysis.
The symbol "::=" may be read "is a",
the symbol "|" may be read "or".
The character strings beginning with "<" and ending with ">" correspond to
"numeral" and "digit" in %21%1 and %22%*;
by convention, components of BNF equations which %6describe%* elements
are enclosed in "<" and ">"; and elements  which are given %6explicitly%*
are written without the "< >" fence.
Thus "<digit>" is not a numeral but is a description; to make the definition
of <numeral> complete we should include an equation like:

.BEGIN TABIT1(15);
.BOXA
<digit>\:: = %30 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9%*
.BOXB
.END
.FP
Juxtaposition of objects implies concatenation of the syntactic objects. Thus
"89" is an instance of "<numeral><digit>".

It will be convenient to have notations for the abstract objects
as well as notations for the syntactic representations. The BNF equations
describe syntactic classes; for example, the set generated by
<numeral> is the syntactic class of numerals⊗↓Note we could have written
<numeral>#::=#<digit> and <numeral>#::=#<digit><numeral>, generating the same
class, but in a different order. Questions of syntax and grammars
will not be stressed in this book. See ⊗↑[Aho#72]↑.←.
When we are talking about a syntactic class of objects we will 
write <object>; when we are talking about the abstract object we will
write %d<object>%1. For example %d<numeral>%1 is the class of natural
numbers.

What should be remembered from the discussion in this section?
We need precise ways of describing the elements of our study 
on data structures. We have seen that inductive definitions are a powerful
way of describing sets of objects. We have seen a variant of inductive definitions
called Backus-Naur Form equations. We will use BNF equations to describe the
syntax of our data structures and our language.

We  have also introduced the  difference  between an  abstract
object  and  a  representation for that object.    
This  distinction has  been  well
studied in philosophy and mathematics, and we will see that this idea
has strong consequences  for the field of  programming  and computer
science.  Abstract objects  and their representations will play 
crucial roles in this text. 
.SS(Symbolic Expressions: Abstract Data Structures)
.FP
We wish to show that the
use of abstraction will benefit the study of data structures and LISP.
To begin our study we should therefore characterize the domain
of LISP data structures in a manner similar to what we did for numbers.

Our objects are called  %2Symbolic Expressions%*.
Our domain of  Symbolic Expressions is named %d<sexpr>%*.
⊗→Symbolic expressions↔← are also known as  %2⊗→S-expressions↔←%*
or %2⊗→S-exprs↔←%*.  

The set of symbolic expressions is defined inductively over a base set
named %d<atom>%*. 
The set %d<atom>%* can itself be defined inductively. We give a
set of BNF equations
for elements of <atom> below, but the essential character of the
domain is  that it represents two kinds of objects: the %2⊗→literal atoms↔←%*
and the integers.
The elements of %d<atom>%* are called %2atoms%*.

.BEGIN TABIT1(19);GROUP;
.P115:
.BOXA
.KRK
<atom>\:: = <literal atom> | <numeral> | -<numeral>
.PT2
<literal atom>\:: = <atom letter> 
\:: = <literal atom><atom letter> 
\:: = <literal atom><digit>
.PT2;
<numeral>\:: = <digit> | <numeral><digit>
.PT2
<atom letter>\:: =%3 A | B | C ... | Z%* ⊗↓We use ellipses here as a convienient abbreviation.←
.PT2
<digit>\:: = %30 | 1 | 2 ... | 9%*
.BOXB
.END;
.FP
A <literal atom> is therefore a string of uppercase letters and digits, subject
to the provision that the %6first%* character in the atom be a letter.


.BEGIN TABIT2(20,35);GROUP;
.BOXA
.KRK
For example:\atoms\non atoms
.PT18;
%3\ABC123\2a
.PT2
\12\a
.PT2
\A4D6\$$g
.PT2
\NIL\ABD.
.PT2
\T\(A . B)
%*
.BOXB
.END;

The characteristics of atoms which most interest us are their distinguishability:
the atom %3ABC%* is distinguishable from the atom %3AB%*. That 
%3"AB"%* is a
part of  %3"ABC"%* is not germane to our current discussion⊗↓However, we
will discuss such topics in {yonss(P27)} on string processing.←.
Similarly, we will seldom need to exploit numerical relationships underlying
the numerals; at most we will use simple counting properties.
Therefore most of our discussions will deal with non-numeric atoms.
Most implementations
of LISP do however contain a large arithmetic entourage.
Many implementations also
give a wider class of literal atoms, allowing some special characters to appear;
for most of our discussion the above class is quite sufficient.

.GROUP;
The domain of Symbolic expressions, called %d<sexpr>%* is defined inductively over
the domain %d<atom>%*⊗↓We will not give the termination clause, 
but it is assumed to hold.←.
.PT24;
.NL;
%21.%*##Any element of %d<atom>%* is an element of %d<sexpr>%*.
.NL;
%22.%*##If %9α%41%1 and %9α%42%1 are elements of %d<sexpr>%*, 
then the %2⊗→dotted-pair↔←%* %3(%9α%41%3.%9α%42%3)%1 is in %d<sexpr>%*.
.PT24
.APART
.FP;
Thus %d<sexpr>%* includes %d<atom>%* as a proper subset. 
The notation we chose for the dotted-pairs is the following:
.BEGIN INDENT 10,10,10;
.BOXA
A dotted-pair consists of a left-parenthesis followed by an
S-expr, followed by a period, followed by an S-expr,
followed by a right-parenthesis.
.BOXB
.END
.FP
For example, let %9α%41%1 be %3(A#.#B)%1 and %9α%42%1 be %3(1#.#T)%1;
then %3(%9α%41%1#.#%9α%42%1)%1 is %3((A#.#B)#.#(1#.#T))%1.

Greek letters %9α%* and %9β%* will be used in the text 
to designate pattern matches. 
In the current context  the pattern matches  will involve
S-expressions; they can match any well-formed S-expression.
For a further example,
let %3(A#.#(B#.#C))%* be %3(%9α%*#.#%9β%3)%1 then
%9α%1 is %3A%* and %9β%* is %3(B#.#C)%1.
These variables are called %2⊗→match-variable↔←s%* or %2⊗→meta-variables↔←%1.

Finally here's a BNF description of the full set of S-expressions.
.BEGIN TURN ON "←";
.BOXA
.P47:
.KRK
←<sexpr> :: = <atom> | %3(%*<sexpr> . <sexpr>%3)
.BOXB
.END;

Notice that if we allow real numbers  as atoms then some care would need to be
exercised when writing S-expressions. 
For example, should %3(3.1.2)%* be interpreted 
as the dotted pair %3(3 . 1.2)%*, 
as the dotted pair %3(3.1#.#2)%*, 
or is it just an ill-formed expression?
Interpretation of such ambiguous constructs will depend on the implementation; such
details are discussed later.

.<<Examples: S-exprs non S-exprs>>
.BEGIN TABIT2(17,46);GROUP;
.BOXA
.KRK
Examples:\S-exprs\non S-exprs
.PT18
%3
\A\A . B
.PT2
\(A . B)\(A . B . C)
.PT2
\(((A . B) . C) . (A . B))\((A . B)) 
%*
.BOXB
.END;
Recall  our caveat on numerals and numbers; it also applies here. The 
set described by <sexpr> is a  %6specific%* syntactic representation of  
  the domain %d<sexpr>%*.
However, the set <sexpr> will be a
convenient notation since it makes explicit  the construction of the composite
S-expr from
its components⊗↓Just as the "successor" notation shows  the  construction
of  the numbers from %30%*. This kind of  notation will  be much more useful
in LISP, since our interest in data structures will  focus on the 
construction process and the interrelationships between components of an
S-expr.←,
and the  notation is also consistent with LISP history.

However there is more to the domain %d<sexpr>%* than  syntax,
just as there is more to %dN%* than positional notation⊗↓%32%*,
II in Roman numerals, 10 in binary, "zwei" in German ... are all 
representations of the same number.←.
What %6are%* the essential features of S-expressions? 
Symbolic expressions are either
atomic or they have two components. 
If we  are confronted with a non-atomic S-expression
then we want a means of distinguishing between the
"first" and the "second" component. 
The "dot notation" does this for us, but 
obviously "(", ")", and "."  of the dotted-pairs are simply
notation or syntax.  We could have just as well represented
the  dotted-pair of %3A%* and %3B%*
as the set-theoretic ordered pair, %3<A,B>%* or
any other notation which preserves the essentials of the domain %d<sexpr>%*.

The distinctions between abstract objects and
their representation 
are quite important. As we continue our study of more and more complex
data structures the  use of an abstract data structure instead of one
of its representations can mean the difference between a clear and clean program
and a confusing and complicated program. 
There are similar gains for us when we study algorithms defined over these
abstract data structures. The less the algorithm knows about the representation
of the data structure, the easier it will be to modify or understand that
algorithm. Indeed you  may have
already experienced this phenomenon if you have programmed.
A program written in a high-level language is almost always more understandable
than its machine-language counterpart.
The high-level program
is more abstract whereas the machine-language program knows a great deal about 
representations.
Finally, if you still doubt that representations
make a difference in clarity, try doing long division in Roman numerals.
We will  say much more about abstraction and representation in algorithms and
data structures as we proceed.
.SS(Trees: Representations of Symbolic expressions)
.FP
Besides the more conventional typographical notations, S-expressions
also have interesting %6graphical%*  representations.
S-exprs have a natural
interpretation as a  structure which we call a LISP-tree or L-tree.
.GROUP SKIP 1;
.GROUP;
Here are some L-trees:

.BEGIN SELECT g;NOFILL;PREFACE 0 MILLS;
.TURN OFF "%","#";
.TURN ON "∞" FOR "%";
.KRK
.BOXA
             /\				    /\ 
            /  \                           /  \ 
           /    \			  /   /\
          /\    /\                       /   /  \ 
         /  \  /  \			∞3A∞*   ∞3B∞*   ∞3NIL∞*
        ∞31∞*   ∞32∞*  ∞3A∞*  /\ 
                 ∞3D∞*  ∞3E∞* 
.BOXB
.END

.APART;
.GROUP;
.select 1;
.FP
We can give an inductive definition:
.PT24;
.NL
%21.%* Any element of %1<atom>%1 is an L-tree. 
.NL
%22.%* If %3n%41%1 and %3n%42%1 are L-trees then 
.PT24;
.BEGIN SELECT g;NOFILL;PREFACE 0 MILLS;
.TURN OFF "%","#";
.TURN ON "∞" FOR "%";
.KRK
.BOXA
             /\				  
            /  \ 
           /    \
          ∞3n∞41∞g    ∞3n∞42∞g
.BOXB
.END
.FP
 also forms an L-tree.
Most important:  there are no intersecting branches. Later  we will talk about more
general structures called list-structures.
.APART

You can see how to interpret S-exprs as L-trees.  The atoms are
interpreted as terminal nodes;  and since non-atomic S-exprs always
have two sub-expressions we can write the first
sub-expression as the left branch of an L-tree and the second sub-expression 
as the right branch.  
.GROUP;
For example:

.BEGIN SELECT g;NOFILL;PREFACE 0 MILLS;GROUP;
.TURN OFF "%","#";
.TURN ON "∞" FOR "%";
.TURN ON "?" FOR "\";
.TABS 25,50;
.KRK
.BOXA
∞3(A . B)∞*      ?∞3(A . (B . C))∞*    ?∞3((A . B) . C)∞*

  /\	      ?	    /\                ?     /\
 /  \ 	      ?	   /  \               ?    /  \
∞3A∞*   ∞3B∞* ?	  /   /\              ?   /\   \ 
              ?	 /   /  \             ?  /  \   \ 
	      ?	∞3A∞*   ∞3B∞*   ∞3C∞* ?	∞3A∞*   ∞3B∞*   ∞3C∞*
.END
.BOXB
.APART

.GROUP
.SELECT 1;
.P102:
Other representations of LISP-trees are possible;
for example %3(A#.#(B#.#C))%1 can be expressed as:
%3
.BEGIN SELECT b;NOFILL;PREFACE 0 MILLS;
.TURN OFF "%","#","α";
.TURN ON "∞" FOR "%";
.KRK
.BOXA
		        ⊂αααπααα⊃            ⊂αααπααα⊃
		  ααααα→~ # ~ #αβααααααααααα→~ # ~ # ~
		        %αβα∀ααα$            %αβα∀αβα$
		          ↓                    ↓   ↓
		          ∞3A∞*                    ∞3B∞*   ∞3C∞*
.BOXB
.END
.APART
.GROUP
%1or:
.BEGIN SELECT b;NOFILL;PREFACE 0 MILLS;
.TURN OFF "%","#","α";
.TURN ON "∞" FOR "%";
.KRK
.BOXA
		        ⊂αααπααα⊃            ⊂αααπααα⊃
		  ααααα→~ A ~ #αβααααααααααα→~ B ~ C ~
		        %ααα∀ααα$            %ααα∀ααα$
.BOXB
.END


.APART
.SELECT 1;
.FP
These last two representations are called %2⊗→box-notation↔←%*.

Please keep in mind the distinction between the abstract 
S-expr  and the several representations
which we have shown.
The question of representation is so important and will occur so frequently that
we introduce notation for a representational mapping, %9r%*.
To represent domain %dD%1 in domain %dE%1, we will define a
function %9r%4D→E%1 which usually will be specified inductively, and
will express the desired mapping.

.GROUP;
For example a representational  mapping %9r%4<sexpr>→L-tree%1 can be given:
.BEGIN CENTERIT;

←%9r%f(%1<atom>%f)%1 = %1<atom>%1
.pt2;
and for %9α%* and %9β%* in %1<sexpr>%1:
.END
.BEGIN SELECT g;NOFILL;PREFACE 0 MILLS;GROUP;
.TURN OFF "%","#";
.TURN ON "?" FOR "\"
.TURN ON "∞" FOR "%";
.TABS 25,37;
.KRK
?∞9r∞f(∞3(∞9α∞* . ∞9β∞*)∞f)∞1 =∞G?    /\
??    /  \
??   /    \
??∞9r∞f(∞9α∞f)∞g   ∞9r∞f(∞9β∞f)∞g
.END
.APART

Typically context will determine the appropriate subscript on the %9r%1-mapping;
thus we will omit it.
.REQUIRE "PROB1.PUB" SOURCE_FILE;
.SS(Primitive Functions)
.SELECT 1;
.FP
So far we have described the domain of abstract objects called
S-exprs and have exhibited several representations for these objects.
We will now describe some functions or operations to be performed on this domain.
We need to be a bit careful here. We are about to see one of the main
differences between mathematics and computer science: mathematics
emphasizes the idea of function; computer science emphasizes the idea of
algorithm, process, or procedure.

.BEGIN "x3" TURN OFF "{,}";TURN ON "#","←";
What is a function? Mathematically a function is simply a
mapping such that for any given argument in the domain of the function there
exists a unique corresponding value. 
In elementary set theory, a definition of function %3f%* involves saying that %3f%*
is a set of ordered pairs %3f#=#{#<x%41%*,#y%41%*>,#...}%1; the %3x%4i%1's are
all distinct and the value of the function %3f%* for an argument %3x%4i%1 is
defined to be the corresponding %3y%4i%1.
No rule of computation is given to 
locate values; with the first definition it is implicit that the internal structure
of the mapping doesn't matter; in the set-theoretic definition, the correspondence
is explicitly given.

An algorithm or procedure is a process for
computing values for a function. The factorial function, %3n!%*,
can be computed by many different algorithms; but as a function it is
a set 
.BOXA
←%3{<0,1>, <1,1>, <2,2>, <3,6>, ...<n,n!>,  ...}%1.
.BOXB
.END "x3"
.FP
The %2domain%1 of a function is the set of all values for which the function is 
defined; the %2range%1 of a function is the set of all values which the function
takes on.
A careful definition of a function requires specification of a 
further set called the %2domain of discourse%1. 
The domain of discourse, named %dD%*,
consists of all possible values which may occur
as the argument to a function.
If the domain of a particular function %3f%* coincides with %dD%* then %3f%*
is said to be a %2⊗→total function↔←%* (over %dD%*); if there are 
elements of %dD%* which are not in the domain of %3f%* then %3f%* is a 
%2⊗→partial function↔←%1, and %3f%* is said to be %2undefined%1 for those values.
For example, the factorial function is typically considered to be partial over
the integers: total for the natural numbers, but undefined for negative integers.
Thus the concept of "total" or "partial" is relative to a specified
domain of discourse.
However, a function %3f%1 total over a domain %dD%41%1 can be extended to be
total over a domain %dD%41%1∪%dD%42%1 by assigning values  to %3f(d)%1 for
%3d%9ε%dD%42%1-%dD%41%1. 
In this way,
 factorial can be extended to be total over the integers
by defining %3n!%1 to be %30%1 for %3n%1 less than %30%1.
We may extend the range of a function when we extend the domain; thus
%3f(d)%1 need not be in the range of the original %3f%1.
For example, we added %30%1 to the range when we extended the factorial
function. When we extend the range
we must specify what additions have been made.

A substantive decision needs to be made on how we are to handle partial 
functions⊗↓Partial functions occur naturally in computation. Most programs
will fail to give results under some circumstances. The function which that
program is computing is a partial function. Some error conditions can produce
error messages; some error conditions may cause
the program to loop. We will analyze both situations.←.
Since we are attempting to be reasonably realistic about our modelling of
computation we should be as precise as possible in our formalism.
We could introduce a class of error values and include them in the range of
%3f%*; these values would be given as the result of applying %3f%*
to an argument not in its domain; or
we could simply say that the result is "unspecified"
⊗↓How "unspecified" manifests itself on  a machine will depend on the implementation.
Sometimes error messages are given; sometimes not.←.
We shall pick an intermediate position; 
we shall introduce %6one%* new element,
%9B%*, called "unspecified" or "undefined", or "bottom"⊗↓"bottom" is
sometimes written %9W%*.←.
We will define all our functions 
over domains augmented with this element;
thus constructs like %3f(%9B%*)#=#a%1 are allowed. For the moment,
think of %9B%1 as covering all anomalous conditions 
which could be detected and printed as error messages; later we will
refine this interpretation.

.P181:
As we define new  data structures we will frequently want to extend
our functions to larger domains. For most of our purposes, 
a function %3f%* defined on (an augmented domain) %dD%* will be extended to 
 a larger domain, 
%dD%1∪%dD%41%1, by defining %3f(d%41%*)#=#f(%9B%*)%1 for 
.P183:
%3d%41%9ε%dD%41%1-%dD%1⊗↓%1The
exception to this extension convention involves the definition of predicates
which can tell whether or not an arbitrary element is in a specified domain.
These predicates always give true or false when applied to any element other than
%9B%1.←,
therefore %3f(%9B%3)%1 need not be %9B%1.
However
 many of the functions which we will examine
are defined such that %3f(...,#%9B%*,#...)#=#%9B%1. 
Functions which possess this property are called %2⊗→strict functions↔←%1.

.GROUP;
To apply this discussion of %9B%* to S-exprs we will define an
extended domain %dS%* to be:
.P251:
.BEGIN CENTER;TURN OFF "}","{";
.BOXA
%dS%* =  %d<sexpr>%1#∪#{%9B%1}.
.BOXB
.END
.APART
.FP
Then we can talk about functions which are total over %dS%* or 
 over %d<sexpr>%*,
and we will talk about functions which are partial over %d<sexpr>%*.
When we ask if an S-expr function  is partial or 
total without specifying
a domain, we are asking the question over the natural, unextended domain, %d<sexpr>%*.

We will now move towards a more algorithmic presentation. We will return to the 
mathematical aspects occasionally, but our main concern in this text
is a treatment of algorithms expressed in LISP. We will continue
to say  "LISP#function" or just "function", but what we are expressing
or describing is a particular algorithm or procedure, not a function
in the mathematical sense. When we wish to stress the distinction we will
use "procedure" or "algorithm".

The first LISP function we consider is 
⊗→%3cons%*↔←. This binary function is used to generate S-exprs from less
complicated S-exprs.  %3cons%* is called a %2⊗→constructor↔←%*-function and
is a  strict function⊗↓For an alternative
interpretation of %3cons%1 see  ⊗↑[Fri#76a]↑.←; it is a total function
over the domain %dS%1. More  precisely,  since %3cons%1
is a %2binary%1 function, each argument of %3cons%1 is free to take on
values from %dS%1⊗↓We could also say that %3cons%1 is total over the
Cartesian product %dS%dx%dS%1.←.
Whenever %3cons%* is presented with two elements %9α%* and %9β%* from %d<sexpr>%*,
%3cons[%9α%*;%9β%*]%1 returns  a new S-expr %3(%9α%*#.#%9β%*)%1. 
Interpreted as a LISP-tree, %3cons[%9α%*;%9β%*]%1 
forms a new LISP tree which has a left branch %9α%*
and has a right branch  %9β%*.  
.GROUP;
.BEGIN "x4" CENTERIT;SELECT 3;
.PT18;
For example:←cons[A; B] = (A . B)
.EQ1(30);
\cons[(A . B); C] = ((A . B) .C)
.END
.END "x4";
.APART
Expressions  which can  have a value, are called %2⊗→forms↔←%1.
S-exprs are forms since they are the constants of our language:
 the value of a constant is that constant.
Function applications are forms: the value is the result of 
performing the designated function on the
designated arguments.

.P127:
Notice that we are designating function application in LISP by 
"function name, followed by a list of arguments delimited by `[' and
`]'⊗↓The syntax equations for forms are given
on {yon(P66)}.←."  The `[...]'-notation is part of the LISP syntax and we will reserve
`(...)'-notation for the function application of mathematics. 
In a few places in our discussions the distinction will be important.
Typically the distinctions will occur when we wish to distinguish between
the LISP algorithm and the mathematical function computed by that algorithm.

A critical distinction has already  arisen in discussing 
forms like %3cons[A;B]%1. The constructor %3cons%1 is actually an algorithm.
Since it is a primitive algorithm it will be represented on a machine
by a sequence of operations which  depend on the implementation of
S-exprs and depend on the primitive operations of the hardware machine.
The %6process%1 of extracting a value from the form %3cons[A;#B]%1
is called %2⊗→evaluation↔←%1. Evaluation is an algorithmic idea; there is no
idea of evaluation involved with the concept of "function".
To reinforce this algorithmic interpretation we will say things like
#a#function returns as value#..." meaning the algorithmic representation
of a function computes and produces a value.

.<<car and cdr>>

We have two strict, unary %2⊗→selector↔←%1 functions, %3car%* and %3cdr%*⊗↓These 
names are hold-overs from the original implementation of LISP on an 
IBM 704. That machine had partial-word instructions to reference the
%da%1ddress and %dd%1ecrement parts of a machine location. The %3a%* of
%3car%* comes from "address", the %3d%* of %3cdr%* comes from "decrement".
The %3c%* and %3r%* come from "contents of" and "register".
Thus %3car%* could be read "contents of address part of register".←, 
for traversing LISP-trees.
We already know the meaning of "strict"; a unary function expects %6one%* argument;
and a selector function is a data structure manipulating function which
will select a component of a composite data structure.
Such LISP functions  are called selectors since they will %6select%1 components of
non-atomic elements of %d<sexpr>%*.
Thus %3car%* and %3cdr%* are ⊗→partial function↔←s over %d<sexpr>%*:
they give values in %d<sexpr>%* only for non-atomic arguments;
they give %9B%* whenever they are presented with an atomic argument.

When given a non-atomic argument, %3(%9α%* . %9β%*)%1,
⊗→%3car%*↔← returns as value the first subexpression, %9α%1;
⊗→%3cdr%*↔← 
(pronounced could-er) 
returns as value the second sub-expression %9β%1.
.GROUP;
.BEGIN "x5" CENTERIT;
.PT18;
For example:←%3car[(A . B)] = A       
.EQ1(32);
\car[A] = %9B%*
\%3cdr[(A . B)] = B
\cdr[(A .(B . C))] = (B . C)
\car[((A . B) . C)] = (A . B)
.END;
.END "x5";
.APART
.GROUP;
We will include ⊗→functional composition↔← as a notation for combining
LISP expressions.
The composition of two unary functions %3f%* and %3g%* is another
function, denoted by %3f%fo%*g%1. The value of an expression, %3f%fo%*g[x]%1,
is the value of %3f[g[x]]%*.
That is, the value of %3f%fo%*g[x]%1 is a %3z%* 
such that %3y%* is the value of %3g[x]%*
and %3z%* is the value of %3f[y]%*. %3f%fo%*g%1 may be undefined for several reasons:
%3g[x]%* may be undefined and  %3f%1 is strict, or %3f[y]%* may be undefined.
.APART
.GROUP
Here are some examples of composition:

.BEGIN "x6" CENTERIT;
.BOXA
.PT18
%3
←car%fo%*cdr[(A .(B . C))] = car[cdr[(A .(B . C))]] = car[(B . C)] =  B 
.PT18
←cdr%fo%*cdr[(A .(C . B))] = cdr[cdr[(A .(C . B))]] = cdr[(C . B)] =  B
.PT18;
←cdr[cdr[A]] = %9B%*
.PT18
←car[cdr[(A . B)]] = %9B%*
.PT18;
←car[cons[X;A]] = X     cdr[cons[Y;X]] = X .
.BOXB
.END "x6";
.APART
.FP
All the functions in these examples are strict;
for that reason, if %3g[x]%1 gives %9B%1 then the composition %3f%fo%3g[x]%1 also
gives %9B%1. That need not be the case if %3f%1 is non-strict.

The composition of many %3car%* and %3cdr%* functions occurs so frequently that an
abbreviation has been developed.  
Given such a composition, we select  in left-to-right order, 
the relevant %3a%*'s and %3d%*'s in the %3car%*'s and %3cdr%*'s. We sandwich this
string of %3a%*'s and %3d%*'s between a left-hand %3c%* and a right-hand %3r%*
and give the composition this name.

.BEGIN CENTERIT;GROUP;
.BOXA
For example:%3←cadr[x] <= car[cdr[x]]
.PT18
←caddr[x] <= car[cdr[cdr[x]]]
.PT18
←cdar[x] <= cdr[car[x]]
.BOXB
.END;
.FP
These compositions are also called %2⊗→%3car-cdr-%*chains%1↔←%1, and are useful in
traversing LISP-trees. The notation "<=" is to be read "is defined to be the 
function ...".
This notation is only a temporary convenience and not part of LISP.
Soon we will study what is involved in giving and using definitions in LISP
({yonss(P49)}).
For the moment intuition will suffice.

.<<discussion of components of function def>>
It is useful  to introduce some terminology for 
 the components of a function definition. Let
.BEGIN CENTERIT; SELECT 3;
.BOXA
←f[x%41%*; ...; x%4n%*] <= %9x%3
.BOXB
.END
represent a typical definition. The %2name%* of the function is %3f%*;
the %2body%* of the function is the expression %9x%1.
 The list
%3[x%41%*; ...; x%4n%*]%1
appearing after the function name
is  called the %2⊗→formal parameter↔←%* list.
The elements of the formal parameter list are called formal parameters
and will play a role similar to that of variables in mathematics⊗↓The 
behavior of formal parameters and variables is %6not%1 identical.
We will say more about the distinction in {yonss(P273)}.←.
Therefore we will also refer to formal parameters as variables.
Lower-case 
identifiers⊗↓%1See {yon(P66)} for the BNF equations for <identifier>.← will be
used  as  variables and function names.  
So for example %3Y%* and %3CAR%1 are atoms; %3y%* 
and %3car%1 could be used as variables.
Be clear on the distinction between LISP variables like %3x, y%* or %3foo%*,
and the match variables⊗↓%1also called meta-variables← like %9α%* or %9β%*.
For %9α%* and %9β%* ranging over S-expressions, %3(%9α%*#.#%9β%*)%1 is a
well formed S-expr. The construction, %3(x#.#y)%*, is %6not%* 
well-formed, but %3cons[x;y]%1 is correct.

A function is %2applied%*  using the common
notation of %2⊗→function application↔←%1:
.BEGIN CENTERIT; SELECT 3;
.BOXA
←f[a%41%*; ...; a%4n%*]
.BOXB
.END
The %3a%4i%1's are called %2⊗→actual parameters↔←%1; for an
application to be well formed, the actual parameters must agree in
number with the formal parameters of the definition  and they
are to be associated in a one-for-one order, %3a%4i%1 with %3x%4i%1.
Thus in the expression %3car[cdr[(A#.#B)]]%* the actual parameter
to the %3car%* function is %3cdr[(A#.#B)]%*, and the actual parameter to
%3cdr%* is %3(A#.#B)%*.
How the actual parameters are to be treated will be a large part of our 
study.

 Again, it is convenient
to introduce some terminology to distinguish between an algorithmic idea and
its mathematical counterpart. The phrase "function#call" is used to
name the procedural counterpart  to "function#application".
LISP is called an %2⊗→applicative#language↔←%1 since it is 
based on the idea of function application.
Mathematically speaking, a composition of functions is simply another function
--#i.e.,#a mapping#-- and therefore nothing need be said about how to compute
composed functions. From a computational point of view, 
we want to  express evaluation
of expressions involving composed functions in terms of the evaluation of
subexpressions. This would allow us to describe a complex computation in terms
of an appropriate sequence of subsidiary computations.
One of the more natural ways to evaluate expressions involving compositions is
to evaluate the inner-most expressions first, then work outwards. 
Assume arguments to multi-argument
functions are evaluated in left-to-right order. Thus:

.BEGIN SELECT 3;GROUP;TABIT2(1,40);
.KRK
.BOXA
\cons[car[(A . B)];cdr[(A . (1 . 2))]]\%1reduces to%3  cons[A;cdr[(A . (1 . 2))]]  
\\%1reduces to%3  cons[A;(1 . 2)] 
\\%1reduces to%3  (A . (1 . 2))
.BOXB
.END

.P106:
Evaluation may seem to be a simple operation but
in fact  evaluation is a very complex process.
The value of an expression may depend on the %6order%* in which we do things. 
For example, consider
the evaluation of %3second[car[A];#B]%1 where %3second[x;y]#<=#y%1.
If we expect %3second%* to be a strict function, then %3second[car[A];#B]%1
must return %9B%*
even though it is reasonable to believe that the value of the computation should
be %3B%1 since %3second%* does not visibly 
depend on the value of its first parameter.
It appears that if we postponed the evaluation of the arguments until
those values were actually needed, then at least this problem would be solved.
However,
the consequences of defining a function to be strict
are severe; they cannot be sidestepped by resorting to different schemes 
for evaluating arguments. There is an alternative, but
not particularly attractive, strategy for assigning
strictness: we could examine the body of the function; if the function uses
all its parameters, then it's strict. If the function doesn't depend on one 
or more parameters, then it's non-strict. Thus with this interpretation, %3second%1
%6is%1 non-strict.  
We prefer the initial interpretation, 
reasoning that, if a function is passed bad information, then we wish to 
know about it, even if the function does not use that specious result.

.GROUP;
Strictness is closely related to evaluation schemes for parameter passing.
 Here are two common techniques:
.BEGIN TABIT1(7);
.P121:
.BOXA
.ONCE indent 0,9;FILL
%2CBV%*####Evaluate the arguments to a function; pass those evaluated arguments to the function.
.BOXB
.END
.FP
This scheme, called %2C%1all %2B%1y %2V%1alue, is what we were informally using to evaluate 
the previous examples.
.APART
.GROUP;

An alternative evaluation process is %2C%1all %2B%1y %2N%1ame:
.BEGIN TABIT1(9);GROUP;
.BOXA
.KRK
.P126:
%2CBN%*\Pass the unevaluated arguments into the body of the function.
.BOXB
.END
.APART
Assuming %3second%1 is defined to be strict, then
%3second[car[A];#B]%1  yields %9B%1 under either %2CBV%1 or %2CBN%1. 
However if we define %3second%1 to be 
non-strict then %2CBV%1 and %2CBN%1 will both give value %3B%1.
With %2CBV%1, %3x%1 is bound to %9B%1; while with %2CBN%1 %3x%1 is bound to %3car[A]%1.

Further relationships between evaluation schemes and strictness 
will be investigated.
On {Yon(P112)} we discuss non-terminating
computations.
In {yonsec(P113)} we will discuss evaluation techniques
and will give a precise characterization of the evaluation of LISP expressions.
On {yon(P40)} we will introduce a non-strict language construct 
but,
until that time, intuitive application of %2CBV%1 will suffice.

We must exercise care
 when discussing the process of evaluation; the function we are
characterizing by  computing its values will often depend on our choice
of evaluation scheme. 

.GROUP;
Before introducing a further class of LISP expressions we summarize
the
syntax of the LISP expressions  allowed so far:

.BEGIN TABIT1(20);GROUP;
.BOXA
.P66:
<form>\::= <constant> | <application> |  <variable>
.PT2
<constant>\::= <sexpr>       (where <sexpr> is given on {yon(P47)})
.PT2
<application>\::= <function-part>[<arg>; ...;<arg>] 
.PT2
<function-part>\::= <identifier>
.PT2
<arg>\::= <form>
.PT2
<variable>\::= <identifier>
.PT2
<identifier>\::= <letter> | <identifier><letter> | <identifier><digit>
.PT2
<letter>\::= %3a | b | c  ... | z  %1
.PT2
<digit>\::= %31 | 2 | ... | 9
.BOXB
.END
.APART;
.P130:
.FP
The use of ellipses in the last equation is an abbreviation we have seen before.
The use of ellipses in the <application> equation is  different. It is
an abbreviation meaning "zero or more occurrences".
Thus the equation means an <application> is a <function-part> 
followed by the symbol "["
followed by zero or more <arg>'s followed by the symbol "]".
This use of ellipses can always be replaced by a sequence of BNF equations. 
for example, this instance can be replaced by:
.BEGIN TABIT1(17);
.BOXA
<application>\::= <function-part>[<arg-list>] | <function-part>[ ] 
.pt2
<arg-list>\::= <arg> | <arg-list>;<arg>
.BOXB
.END
.FP
To improve readability
we will frequently violate these syntax equations, allowing function names
containing special characters, e.g. %3fact*%*, %3fib%9'%1 or + ; or writing %3x+y%*
instead of %3+[x;y]%*.  No attempt will be made to characterize these violations;
occurrences of them should be clear from context.

.GROUP;
Notice that the class <⊗→form↔←> is a collection of LISP expressions which can
be evaluated. A <form> is either:
.PT24
.NL
%21.%*##a constant: the value is that constant.
.NL
%22.%*##an application: we've said a bit about evaluation schemes for these constructs.
.NL
%23.%*##a variable: a variable in LISP will typically have an associated value in some
environment.
.PT24
.APART
.FP
We will wait to {yonss(P49)} for a precise description.

.P111:
An important constraint on LISP forms which is not covered by the syntax
equations is the requirement that functions are defined as being n-ary for
some %6fixed%* n.  Any  n-ary LISP function
must have %6exactly%* n arguments presented to it whenever it is 
applied.
.P95:
Thus %3cons[A], cons[A;B;C], %*and %3car[A;B]%* are all ill-formed expressions
and  therefore denote %9B%1.
.PT24
.CENT(Problems)
.NL
1.##Discuss %3cons[car[x];cdr[x]] = x%1.
.NL
2.##Discuss %3cons[car[%9α%*];cdr[%9α%*]] = %9α%1.
.SS(Predicates and Conditional Expressions,conditional expression)
.FP
We cannot generate a very exciting theory based simply on %3car, cdr,%* and %3cons
%*
with functional composition. Before we can write reasonably interesting 
algorithms we must have some way of performing conditional actions.
To do this we first need ⊗→predicates↔←. A LISP predicate is a function
returning a value representing truth or falsity.  We will represent the
concepts of true and false by %et%* and %ef%* respectively. Since these truth
values are distinct from elements of %dS%*, we will set up a new domain %dTr%*
which will consist of the elements, %et%* and %ef%*. As usual 
the extra element %9B%1 is
included so that we may talk about partial predicates just as we 
talked about partial functions on %d<sexpr>%*.⊗↓A word for the 
previous LISP user: our use of %et%* and %ef%* marks our first major
break from current LISP folklore. 
The typical LISP trick is to use the atoms %3T%1 and %3NIL%1 
rather than %et%1 and %ef%1 as truth values. 
Our convention will disallow some mixed compositions of LISP
functions and predicates.←.

LISP has two primitive predicates.
The first is a strict unary predicate named ⊗→%3atom%*↔←;
%3atom%* is total over %d<sexpr>%*, and
is a special kind of predicate called a %2⊗→recognizer↔←%1 or a %2⊗→discriminator↔←%1.
Recognizers are used to determine the type of an instance of a data structure.
Thus %3atom%* will return %et%* if the argument denotes an atom, and will return %ef%*
if the argument is a non-atomic S-expr.
.GROUP SKIP 1;
.BEGIN "x7" CENTERIT;
.GROUP
.EQ
%3atom[A] = atom[NIL] = %et%*
.EQ1(28)
\atom[(A . B)]  = %ef%*
\atom[car[(A . B)]]  = %et%*
\atom[%9B%3] = %9B%3
.END
.BOXB
.APART
.END "x7";
.GROUP;
What should we do about the value of constructs like:
%3cons[atom[A];#A]%1? %3atom[A]%1 gives %et%1, but %et%1 is not an element of %dS%* and
thus is not appropriate as an argument to %3cons%1. Using our discussion of 
{yon(P181)},
we extend the domains of the S-expr primitives to
.P184:
.EQ
%dS%41%1 = %dS%1∪%dTr%1
.PT18
.APART
.BEGIN "x8" CENTERIT;SELECT 3; GROUP;
%1For example,  for %3s%9ε%dTr%1:%3
.EQ
car[s] = car[%9B%3],   cons[s; A] = cons[%9B%3; A]%1 
.PT18
.END "x8"
Since all those functions were strict with respect to undefined we have:
.BEGIN "x9" CENTERIT;SELECT 3; GROUP;
.EQ;
atom[%Et%3] = %9B%3
.EQ1(34);
\cons[%9B%3; A] = %9B%3
\cons[A; %9B%3] = %9B%1
.END
.BOXB
.END "x9"

Notice that we now have %6two%* separate domains: S-expressions and truth values.
Since we will be writing functions over several domains we will need a 
general recognizer for each domain to assure that the operations defined on each
abstract data structure are properly applied. Thus we introduce  the recognizer
%3issexpr%* which will give %et%* on the domain of S-exprs, 
%ef%1 for
for any element  not in %d<sexpr>%1 and will give %9B%1 for  %9B%1.

.BEGIN "x10" CENTERIT;SELECT 3;GROUP;
.EQ
issexpr[(A . B)] = issexpr[A] = %et%*
.EQ1(24);
\issexpr[%et%*] = %ef%*
\issexpr[%9B%*] = %9B%*
.END
.BOXB
.END "x10"

Another primitive predicate we need is named ⊗→%3eq%*↔←.  
It is a strict binary predicate, partial over the set %d<sexpr>%*;
it will give a truth value only if  its arguments are both atomic.  
It returns %et%* if the arguments denote  the
same atom; it returns %ef%* if the arguments represent different atoms.
%3eq%1 yields %9B%1 if either argument to %3eq%1
denotes an element not in the set %d<atom>%1.
.BEGIN TABIT2(17,43);
%3
.BOXA
.GROUP
\eq[A;A] = %et%*\eq[A;B] = %ef%*
.PT18
\eq[(A . B); A] = %9B%3 \%3eq[(A . B);(A . B)] = %9B%3
.PT18
\eq[eq[A;B];D] = %9B%3 \eq[%9B%3;x] = %9B%3
.PT18
\eq[car[(A . B)];car[cdr[(A . (B . C))]]] = %ef%1
.BOXB;
.END
We should define a version of %3eq%*, say %3eq%4Tr%1, which
is defined over %dTr%* and acts like %3eq%*; rather, we will
simply extend the definition of %3eq%* to %dS%41%1 so that it may compare two elements of
%dTr%*.

.BEGIN "x11" TABIT2(23,40);
.BOXA
%3
.GROUP
\eq[%et%*;%et%*] = %et%*\eq[%ef%*;%9B%3] = %9B%3
.PT18
\eq[%ef%*;%ef%*] = %et%*\eq[%et%*;%ef%*] = %ef%*
.PT18;
\eq[A;%et%*] = %9B%1
.APART;
.BOXB
.END "x11"


We need to include a construct in our
language to effect  a test-and-branch operation.
In LISP this operation is indicated by the %2⊗→conditional expression↔←%1.  It
is written:
.BEGIN CENTERIT;

%3
←[p%41%* → e%41%*; p%42%* → e%42%*; ... ; p%4n%*  → e%4n%*]
%1
.END
.FP
.P40:
Each %3p%4i%1 is an expression which takes on values in the
set %dTr%* or gives %9B%1; 
each %3e%4i%1 is an expression which will  give a value in
%dS%41%1. We will restrict the conditional expression such that all the %3e%4i%1
must have values in the %6same%1 domain or be %9B%1; i.e. all be in %d<sexpr>%1
or all be in %dTr%1.
.GROUP;
Assuming that an instance of a conditional expression meets this restriction,
the rule for evaluation is given by the following:

.BEGIN INDENT 10,10,10;group
We evaluate the %3p%4i%1's from left to right, finding the %6first%*
which returns value %et%*.  When we find such a %3p%4i%1, 
we evaluate the corresponding
%3e%4i%1.  
The value of the conditional expression is the value computed by that %3e%4i%1; 
if all
of the %3p%4i%1's evaluate to %ef%* then the conditional expression gives %9B%1.
The conditional expression  also gives %9B%1 if we come across a %3p%4i%1
which  has value %9B%1 before we hit a %3p%4i%1 with value %et%1.
.END
.APART;
.BEGIN "x12" CENTERIT;
.GROUP;
Examples:
%3
.EQ
[atom [A] → B; eq [A;(A . B)] → C] = B
.pt18
.BEGIN FILL;SELECT 1;
.fp
Notice that the p%42%* expression of the first example is undefined, but
the conditional gives value %3B%* since p%41%* gives value %et%*;
this means that
conditional expressions are non-strict. 
.END
.APART
.group;
.BEGIN "X12A" tabit1(19);
\[eq [A;(A . B)] → C; atom [A] → B] = %9B%3
.BEGIN FILL;SELECT 1;
.FP
Here a reordering makes the  evaluation return %9B%1.
.END
.apart;
.pt18;
.group;
\[atom [(A . B)] → B; 
\ eq [A ; B] → C; 
\ eq [car[(A . B)]; cdr[(B . A)]] → E] = E
.BEGIN FILL;SELECT 1;
.FP
This example is more complex so, to improve readibility, we split
the conditional clauses across several lines. This stylistic formatting
is called ⊗→%2pretty printing%1↔←.
.END
.APART
.pt18;
\[eq [A; A] → %et%3; atom [A] → %ef%3] = %et%3
.pt2;
\[eq [A; A] → %et%3; atom [A] → %3B%3] = %9B%3
%1
.END "X12A"
.END "X12"
.APART
Note  that non-strictness
is relative to a single domain; thus the last example above gives %9B%1 since
it contains %3e%4i%1's of differing domains.

.BEGIN TURN ON "#";
Frequently it is convenient to use a special form of the conditional expression
where the final %3p%4n%1 is guaranteed to be true. 
There are many expressions which always evaluate to %et%1;
#%3eq[1;1]%* is one.  The simplest expression is the
constant %et%*.
.END

.BEGIN CENTERIT;

Consider the special form:←%3[p%41%*  → %3e%41%*; ...; %et%* → %3e%4n%*]
%1
.END
If we know that the previous
%3p%4i%1's are either true or false⊗↓and we know that all the %3e%4i%1's are
elements of the same domain.←, 
the final %3p%4n%1#→#%3e%4n%1-case is a catch-all
or otherwise-case which will be executed if none of the previous %3p%4i%1's
give %et%*.
Thus the use of %et%* in this context can be read "otherwise";
and the conditional can be read:

.BEGIN CENTERIT;
.pt18;
←"If %3p%41%1 is true then %3e%41%1, else if %3p%42%1 is true then ..., otherwise %3e%4n%1."
.END
.PT18;
.P17:
The introduction of conditional expressions has further widened the gap between
traditional mathematical theories and computational theories. 
Previously we could almost side-step the issue of order of evaluation; 
it didn't really matter unless %9B%* was involved. But now
the very definition of meaning of conditionals involves an order of evaluation. 

The order of evaluation is important from a computational
viewpoint: if we are going to give as value
the leftmost %3e%4i%1 whose %3p%4i%1 evaluates to %et%*, then there is
no need to compute any of the other %3e%4j%1's; those values will never be used.
A more pressing difficulty is that of partial functions. If we did not
impose an order of evaluation on the components of a conditional, then
frequently we would attempt to evaluate expressions which would lead
to undefined results: %3[eq[0;0]#→#%31%*;#%et%*#→#car[A]]%1 gives %31%*
using the meaning of conditionals, whereas the expression would be undefined 
if we were required to evaluate %3car[A]%*. If
we think of an occurrence of %9B%1   being
mapped to an error message, 
evaluating %3car[A]%1 would cause termination of the computation.
But, if we continue to allow
%9B%* as an argument or value, then we can characterize
the effect of a conditional expression as a %2⊗→non-strict↔←%* function.
Recall, a non-strict function is allowed to return a value other than %9B%* 
when one of its arguments is %9B%*; or, put another way, we don't examine
the definedness of arguments before applying the function.

For example,
let %3if(x;y;z)%1 be the %2conditional function%1 ⊗↓Notice we are 
writing `(...)' rather than `[...]' since we are talking
about the function and not the algorithm. See {yon(P127)}.← 
computed by: %3[x#→#y;#%et%*#→#z]%1.
We can define %3if%* as a non-strict function
such that:

.BEGIN TABIT2(20,35);GROUP;
.BOXA
\\%3y%* if %3x%* is %et%*
\%3if(x;y;z) = \z%1 if %3x%* is %ef%*
\\%9B%* if %3x%* is %9B%*
.BOXB
.END

.P112:
However there is more to the "strictness" implied by conditional
expressions than just making sure that proper arguments are passed on function
calls.

.group
Consider the following algorithm:

.BEGIN CENTERIT; SELECT 3;
←one[x] <= [x=0 → 1; %et%*  → one[x-1]]
.END
.apart
.FP
Assume that %3one%* is non-strict and
assume the domain of discourse is the  integers.
That means,
%3one%1 will try to compute with %6any%1 (integer) argument it is given.
The  algorithm for %3one%1 defines a function giving %31%* for 
any non-negative integer and
is undefined for any other number. From a computational point of view, however,
%3one[-1]%* appears "undefined" in a different sense from %3car[A]%* being
"undefined". 
The computation %3one[-1]%1 does not terminate and is said to %2diverge%1.
For a partial function like %3car%*, we can 
give an error message whenever we attempt to apply the function
to an atomic argument, but we cannot expect
to include tests like "if the  computation %3f[a]%* does not terminate then
give error No. 15."⊗↓A discussion of such topics
involves a description of the "halting problem" for computational
devices. See ⊗↑[Rog#67]↑ for details.←.  From the purely
functional point of view, %3one%1  still defines the partial function
which is %31%* for the non-negative integers, but computationally there's
an important distinction to be made.

So we see that a computation may be "undefined" for two reasons:
it involves a non-terminating computation or it involves applying a 
partial function to a value not in its domain⊗↓Compare %7w%1-undefined
and E-undefined in ⊗↑[Mor#68]↑.←.
Note that the distinction between "undefined" and "diverges" is fuzzy. If we
restrict  the domain of %3one%1  to the natural numbers, then %3one[-1]%1
denotes %9B%1 rather than diverges. Or, put another way, "undefined strictness"
is a special case of "divergent strictness" where we are able to predict
which computations will not terminate. Those cases can be checked by
defining the function to be strict over a domain which rules out those anomalies.
Thus a case can be made for identifying divergent computations
with %9B%1; however there is typically more to
non-termination that just "wrong kind of arguments".

We want to extend our discussion of strictness to encompass
divergence. Recall the discussion on {yon(P106)} of 
%3second[x;#y]#<=#y%1.
Defining %3second%1 to be strict required that each application of %3second%1
determine whether either argument denoted %9B%1.
If we want %3second%1 to be strict with respect to divergence, then
we must test each argument for divergence. That implies evaluation of 
each of the arguments,
which in turn implies that if a computation of an argument diverges, then the computation
of the function application must also diverge.
This implies that it is natural to associate "strict with respect to divergence"
with %2CBV%1, since in the process of checking for termination, we must compute 
values. However  if a function is strict then 
calling style doesn't matter.

In contrast, a non-strict function does not check arguments for divergence, and
indeed the divergence of a computation may depend on the calling style.
Consider  the evaluation of %3second[one[-1];#B]%1 
where %3one%1 is
total over the integers. This evaluation will diverge under %2CBV%1 while it
converges to %3B%1 using %2CBN%1.
We cannot require all our functions to be strict if we expect to do any  
non-trivial computation.
That is, we need a function which can determine  its value without 
computing
 the values  of all  of its arguments  --a "don't care  condition"--.   
.P180:
.P88:
The conditional function is such  a non-strict function.
That is  %3if(%et%*;q;r)%1  has value %3q%*  without
knowing  anything  about  what  happens  to  %3r%*.  
In particular,
%3if(%et%*;q;%9B%*)#=#q%1.  
Likewise %3if(%ef%*;%9B%*;r)#=#r%1.
Now since %3if%* is to be a function and therefore single-valued,
if %3if(%et%*;q;%9B%*)#=#q%1   then for any argument %3x%*,
%3if(%et%*;q;x)#=#q%1.  
Notice that %9B%* is now carrying an additional "don't-care" interpretation; 
this is   consistent 
with its previous meaning when we think of the function being computed
by the algorithm.

Even given that a computational definition is desired,
there are other plausible interpretations of conditionals.
Consider the definition:
%3g[x;y]#<=#[lic[x]#→#1;%et%3#→#1]%1. Assuming that %3lic%* is a total predicate, 
any value computed by %3g%* will be %31%*. But requiring  left-to-right evaluation
could spend a great deal of unnecessary computation if %3lic%* is a 
%3l%*ong %3i%*nvolved %3c%*alculation.
Questions of evaluation are non-trivial. 
We will spend 
two chapters, {yonsec(P113)} and {yonsec(P274)}, discussing LISP evaluation and
its possible alternatives.


.P131:
What benefits have resulted from our study of %9B%* and divergence?
We should have a clearer understanding of the difference between
function and algorithm and a better grasp of the kinds of difficulties
which can befall  a computation.
We have uncovered an important class of detectable errors.
The character of these miscreants is that they occur in the
context of supplying the wrong %6kind%* of argument to a function. This
kind of error is called a %2⊗→type fault↔←%*, meaning that we expected
an argument of a specific type, that is from a specific domain, 
and since it was not forthcoming, we
refuse to  perform any kind of calculation. 
Thus %3atom[%ef%*]%1 and %3cons[%et%*;A]%1 are undefined
since both expect elements of %dS%* as arguments.
Divergent computations are equally repugnant but there is no general
method for testing whether an arbitrary calculation will terminate.


It may not seem like you can do much useful computation with such
a limited collection of operations as those proposed in LISP. 
Things are not quite as trivial as they might seem.
In elementary number
theory all you have is zero and some simple functions, and elementary number theory
is far from elementary.
Manipulation of our primitives, with composition, and conditional expressions, 
coupled with techniques for definition can %6also%* become complicated.

Let's apply the LISP constructs which we now have, and   define
a  new LISP function.
For example: our predicate %3eq%* is defined only for atomic arguments.  We would like
to  test for equality of arbitrary S-exprs.  
What should this more complex equality mean?
By equality we mean: as trees, the S-exprs have the same branching structure; and
the corresponding terminal nodes are labeled by the same atoms.
Thus, we would
like to define a predicate, ⊗→%3equal%*↔←, such that:
.GROUP SKIP 1;
.GROUP
.BEGIN CENTERIT;
%3
.EQ
equal[(A . B);(A . B)] = %et%* 
.EQ1(27);
\equal[A;A] = %et%3
\equal[(A . B);(B . A)] = %ef%*
\equal[(A . (B . C));(A . (B . C))] = %et%*
\equal[(A . (B . C));((A . B) . C)] = %ef%*
.END
.PT18;
.END
.APART

.FP
Here's an informal description of the %3equal%1 predicate.
.PT24;
.NL
%21.%1##If both arguments are atomic then see what %3eq%* says about them.
 We can test if they are both atomic by using %3atom%*
and a conditional expression.
.NL;
%22.%1##If one is atomic and the other is not they can't be equal S-exprs.
.NL
%23.%1##Otherwise both are non-atomic S-exprs.  Both have two sub-expressions.
Look at both first subexpressions.  If these sub-expressions are not
equal then the original expressions cannot  be equal either.
If the first subexpressions %6are%1 equal then the question of
whether or not the original expressions are equal depends on the
equality   of the second subexpressions.  Thus the
following definition:
.PT24;
.BEGIN TABIT1(20);GROUP;
.BOXA
.SELECT 3;
.P1:
     equal[x;y] <=\[atom[x] → [atom[y] → eq [x;y]; %et%* → %ef%*];
\ atom[y] → %ef%*;
\ equal [car[x];car[y]] → equal[cdr[x];cdr[y]];
\ %et%* → %ef%*]
.BOXB
.END
Notice that we use nested conditional expressions in %3equal%*: e%41%*
is itself a conditional. Also we have used predicates in the e%4i%* positions
at e%43%* and e%411%*; this is allowable since %3equal%* is a predicate.

Let's show that %3equal%* does perform correctly for a specific example.  This will
also show a complicated evaluation of a conditional expression.
We will use the call-by-value rules.
We will perform the evaluation by substituting  the 
evaluated actual parameters for the 
formal parameters in the body of the definition. Then we will simplify the
resulting expression. This is %6not%1 the 
method LISP uses to perform call-by value, but has the same effect.

.BEGIN TABIT1(10);GROUP;SELECT 3;
.EQ
equal[(A . B);(A . C)] %1reduces to:%3
.PT18;
\[atom[(A . B)] → [atom[(A . C)] → eq [(A . B);(A . C)]; %et%* → %ef%*];
\ atom[(A . C)] → %ef%*;
\ equal[car[(A . B)];car[(A . C)]] → equal[cdr[(A . B)];cdr[(A . C)]];
\ %et%* → %ef%*]
.BOXB
.APART
.BEGIN FILL;SELECT 1;
.FP
We find that p%41%* (i.e.,#%3atom[(A#.#B)]%*#)
and p%42%* (#%3atom[(A#.#C)]%*#) when evaluated (in order) give %ef%*.
We must now evaluate p%43%*, which is: %3equal[car[(A#.#B)];car[(A#.#C)]]%*.
This reduces to %3equal[A;A]%1, and:
.END

.GROUP;
.BEGIN TABIT2(7,24);GROUP;
.BOXA
\  equal[A;A] =\[atom[A] → [atom[A] → eq[A;A]; %et%* → %ef%*];
\\ atom[A] → %ef%*;
\\ equal [car[A];car[A]] → equal[cdr[A];cdr[A]];
\\ %et%* → %ef%*]
.BOXB
.END
.APART
.BEGIN FILL;SELECT 1;
This conditional expression will  evaluate to %et%*. So p%43%* in the
original call of %3equal[(A#.#B);(A#.#C)]%* is true and
we must evaluate the  e%43%* expression 
which is %3equal[cdr[(A#.#B)];cdr[(A#.#C)]]%*. That expression simplifies
to %3equal[B;C]%1 and we call %3equal%1.
After  substitution 
and simplification
%3equal%* will finally
return value %ef%*. 
That means that %3equal[(A#.#B);(A#.#C)]%* gives %ef%1.

Clearly, evaluation of LISP expressions in this amount of detail is not a process
which we wish to do very often. It might  be surmised that such a process
is a  candidate for execution by a machine.
Notice that 
%3eq[(A#.#B);(A#.#C)]%* appeared  but was  never evaluated because
of left-to-right evaluation scheme of conditional expressions.
.END
.END
Finally, to include conditional expressions in our syntax of LISP
expressions, we should add:

.BEGIN TABIT1(22);
.BOXA
<form>\::= <conditional expression>
.PT2
<conditional expression>\::= [<form> → <form>; ...; <form> → <form>]    

where <form> was defined on {yon(P66)}.
.BOXB
.END
.FP
These syntax equations fail to capture all of our intended
meaning. For example, the <form>s appearing in the p%4i%*-position are 
restricted to 
be forms taking values in %dTr%*, the truth domain. That restriction is not
expressed in the equations, and indeed, is difficult to express
naturally in such syntax equations. 
See ⊗↑[Hop#69]↑ for a discussion of expressibility
and grammars.
.REQUIRE "PROB2.PUB" SOURCE_FILE;
.REQUIRE "PROB3.PUB" SOURCE_FILE;

.SS(Sequences: Abstract Data Structures,,P100:)
.FP
.BEGIN TURN ON "#";
In several  areas of mathematics it is convenient  to deal
with  sequences  of information. For example, a problem domain  
may be more naturally 
described as  ordered collections of numbers rather than individual numbers.
This may either simplify understanding of the problem or 
simplify the formulation of the functions defined on the domain.
Several
 programming  languages  include  arrays as 
representations of  these mathematical ideas.  
We should notice that sequences
are data structures. We will have to describe constructors, selectors, and
recognizers for them. 
Subsequently
we will explore applications of sequences as data structures.

After a certain familiarity is gained in the application of algorithms which
manipulate sequences, we will discuss the problems of representation and 
implementation of this data structure. We will first give an implementation
of sequences in terms of S-expressions. That is, we will describe an
%9r%*-mapping giving a representation of sequences and their primitive operations
in terms of LISP's S-exprs and primitive functions. 
Still later in {yonss(P137)}
we will discuss low-level implementation of this data structure in terms of
conventional machines.

But now we will study sequences as abstract  data
structures:  what are  their  essential structural  characteristics?  
What properties should  be present in a programming language to allow
a natural  and flexible  representation?   This discussion  will shed
light on the important problems of representation and abstraction. 

A sequence is  an ordered set of elements⊗↓%1For an alternative description
of sequences and a discussion of a different view of data structures see
{yon(P147)}.←.
For example, %2(x%41%*, x%42%*, x%43%*)%1, is standard notation for 
a sequence of  the three elements  %2x%41%*, x%42%1, and %2x%43%1.
The length of a sequence is defined to be the number of elements in that sequence.
We will allow sequences to have
sub-sequences to an arbitrary finite depth.
That is, the elements of a sequence will either be individuals or may themselves be
sequences. 
For example, a sequence of length %3n%*, each of whose elements are sequences of
length %3m%*, is a matrix.
Here are BNF equations for sequences and their elements:

.P114:
.BEGIN TABIT1(19);
.GROUP;
.PT24
<seq>\::= %2(%* <seq elem>, ...,<seq elem> %2)%* ⊗↓For the meaning of these ellipses see
{yon(P130)}.←
.PT2;
<seq elem>\::= <indiv> | <seq>
.PT2;
<indiv>\:: = <literal indiv> | <numeral> | -<numeral>
.PT2
<literal indiv>\:: = <indiv letter> 
\:: = <literal indiv><indiv letter> 
\:: = <literal indiv><digit>
.PT2
<numeral>\:: = <digit> | <numeral><digit>
.PT2
<indiv letter>\:: =%2 A | B | C ... | Z%*
.PT2
<digit>\:: = %20 | 1 | 2 ... | 9%*
.APART;
.END;
.PT24
.FP
Notice that the structure of <indiv> is the same as that for LISP's <atom>;
the only difference is in the fonts used for letters and digits. We have
made the distinction between LISP atoms and sequence individuals intentionally.
Thus %2(A,#(B,#C),#D,#(E,#B))%* is a sequence of length four, whose second
and fourth elements are also sequences.  
We will use "%2(#)%*" as notation for the empty sequence.

We  want to write LISP-like functions operating  over sequences, so we will
at least  
need to give constructors, selectors, recognizers, and predicates for sequences.
 As in the case of S-exprs,
we will include the undefined element, and
the full domain of sequences will be named  
.BEGIN CENTER; TURN OFF "{","}";
.BOXA
%dSeq%1 = %d<seq>%1∪{%9B%1}.
.BOXB
.END

As on {yon(P184)}, we extend the primitive LISP operations
to include this new domain, by defining:
.BEGIN CENTER; TURN OFF "{","}";
.BOXA
%dS%42%1 = %dS%41%1∪%d<seq>%*,
.BOXB
.END
.FP
and extend each operation appropriately over %dS%42%1. For example:
.BEGIN "X12" CENTERIT;SELECT 3;GROUP
.EQ
atom[%2A%3] = %9B%3
.EQ1(34);
\car[%2A%3] = %9B%3
\car[%2(A, B)%3] = %9B%3
\cons[%2A%1; %2B%3] = %9B%3
\issexpr[%2(A)%3] = %ef%3
.END
.PT18;
.END "X12"

We need to define some data structure operations specific to sequences.
What are the essential characteristics of a sequence? First, a sequence
either is empty or  has elements. Thus we will want a predicate to test for emptyness.
Next, if the sequence is non-empty, we should be able to select elements. Finally,
given some elements, we should be able to build a new sequence from them.

The basic predicate, which tests for emptyness, is called ⊗→%3null%*↔←.
Predicates on sequences are like predicates on S-expressions, 
mapping sequences to truth values in %dTr%*⊗↓The 
reason for restructuring LISP predicates might now be apparent
to previous users of LISP: if we mapped the truth values to
the atoms %3T%* and %3NIL%* as is typically done, then we'd have to
map truth values of sequence-predicates to representations as sequence 
elements, and
we would have to perpetuate that decision for every new abstract data structure
domain that we wanted to introduce.←.

.BEGIN "X13" CENTERIT;
.BEGIN TABIT2(10,23);
.BOXA
\\%et%1 if %3x%* is the empty sequence, %2(#)%*.
\%3null[x]%1 is \%ef%* if %3x%* is a non-empty sequence.
\\%9B%* otherwise.
.BOXB
.END
.EQ
%3null[%2( )%*] = %et%*
.EQ1(32);
\%3null[%2(A, B)%*] = %ef%*
\%3null[%ef%*] = %9B%1
.PT18
.END
.BEGIN FILL
Thus %3null%* gives usable values only for sequences.
Since we intend to operate on domains which contain data structures other than
sequences, we will need a ⊗→recognizer↔← to be sure that %3null%* is
not applied to arguments which are %6not%* sequences.
We will name this recognizer ⊗→%3isseq%*↔←.
.END
.EQ
%3isseq[%2(A, B, C)%*] = %et%*
.EQ1(28);
\%3isseq[%2A%*] = %ef%1
\%3isseq[%3A%*] = %ef%1
\%3isseq[%et%*] = %ef%1
\%3isseq[%2()%*] = %et%1
\%3isseq[%9B%*] = %9B%1
.PT18
.END
.BEGIN FILL;TURN ON "#";
The predicate
%3isseq%* is  total over all domains, whereas
%3null%* is only partial: total over %d<seq>%1, but undefined for S-exprs.

While on the subject of predicates, there are a couple more we shall need.
The first one is a recognizer, %3isindiv%*, which will give value %et%*
if its argument is an individual, give %ef%* if its argument is a sequence,
and will give %9B%1 otherwise.

The second predicate is the extension of the equality relation to the class
of sequence individuals. We shall use the same name,  %3eq%*, as 
we did for the S-expression  predicate.
In fact, whenever we define a new abstract data type we will assume that
an appropriate version of %3eq%* is available for the elements of the base
domain. One of our first tasks will be to extend that equality relation to the whole
domain. We will do so for sequences later in this section. 
Equality is 
a basic relation in mathematics so it is not surprising to see it play an
important role here.
%3eq%* is one
of the few relations which we shall define across all domains. 
Functions or predicates like %3eq%1, which are 
applicable on several domains, are called %2⊗→polymorphic functions↔←%*.


.END
.GROUP
.BEGIN FILL;

Next, the selectors for a (non-empty) sequence include: %3first%*, %3second%*, ...#,etc,
where:
.END
.EQ
%3first[%2(A, B, C)%*] = %2A%*
.EQ1(32);
\%3second[%2(A, B, C)%*] = %2B%*
\%3third[%2(A, B)%*] = %9B%1
.END
.PT18
.APART
.GROUP
.BEGIN FILL
It is also convenient to define an "all-but-first" selector, called ⊗→%3rest%*↔←.
.END
.EQ
%3rest[%2(A, B, C)%*] = %2(B, C)%*
.EQ1(30);
\%3rest[%2(B, C)%*] = %2(C)%*
\%3rest[%2(C)%*] = %2()%*
\%3rest[%2C%*] = %9B%1
\%3rest[%2( )%*] = %9B%1
.PT18;
.END
.APART
.GROUP
.BEGIN FILL
In conjunction with %3rest%*, we shall utilize a constructor, ⊗→%3concat%*↔←,
which is to  add a single element to the front of a sequence.
.END
.EQ;
%3concat[%2A%*;%2(B,C)%*] = %2(A, B, C)%*
.EQ1(27);
\%3concat[%2A%*;%2(#)%*] = %2(A)%*
\%3concat[%2(A)%*;%2(B,C)%*] = %2((A), B, C)%*
\%3concat[%2(B,C)%*;%2A%*] = %9B%1
\%3concat[%2A%*; %2B%*] = %9B%1
.PT18
.END
.APART

.END "X13"
.GROUP
.SELECT 1;
The final constructor is called ⊗→%3seq%1↔←; it takes an arbitrary number of sequence
elements as arguments and returns a sequence consisting of those elements (in the
obvious order).
Let %9α%41%1,#...,#%9α%4n%1 be elements of <seq elem>, then:

.BEGIN CENTERIT;SELECT 3;
.BOXA
←seq[%9α%41%3; %9α%42%3; ...; %9α%4n%3] = %2(%9α%41%2, ..., %9α%4n%2)%1
.BOXB
.END
.APART

One question may have come to mind: how do we know when we have a sufficient set
of functions for the manipulation of an abstract data structure?
How do we know we haven't left some crucial functions out? If we have enough,
how do we know that we haven't included too many? 
Actually, this second case isn't disastrous, but when implementing the functions
it would be  nice to minimize the number of primitives we have to program.
These problems are worthy of study and are the concern of anyone
interested in the design of programming languages. We will say a bit more
about solutions to these questions beginning on {yon(P116)}.

Notice that we have been describing the sequence functions 
without regard to any underlying representation.
We have said nothing about these sequence operations except that they
construct, test, or select.
What we are doing is considering sequences as abstract data structures,
suitable for manipulation by LISP-like algorithms. How sequences are represented
as S-exprs or  represented on a machine,
is irrelevant. Sequences have
certain inherent structural properties and it is those properties which
we must understand %6before%* we begin thinking about representation.
In the next section  we will show how to represent sequences 
as certain S-expressions and sequence operations as
LISP operations on that representation.
.END

Let's develop some expertise in manipulating sequences.
The first example will be an extension of the equality relation
to sequences. We perpetuate the name %3equal%* from S-exprs, and the basic
structure of the definition will parallel that of its namesake; but
the components of the definition will involve sequence operations rather
than S-expr operations. It will be of value to compare the two predicates.
The S-expr version is to be found on {yon(P1)}.

.BEGIN TABIT2(19,27);GROUP;SELECT 3;
.BOXA

     equal[x;y] <=\[null[x] → [null[y] → %et%*; %et%* → %ef%*];
\ null[y] → %ef%*;
\ isindiv[x] → [isindiv[y] → eq[x;y]; %et%* → %ef%*];
\ isindiv[y] → %ef%*;
\ equal[first[x];first[y]] → equal[rest[x];rest[y]];
\ %et%* → %ef%*]
.BOXB
.END
.FP
This %3equal%1 works on sequences and sequence  elements
as its S-expr counterpart worked on dotted pairs and atoms.


Next, we will write a predicate  %3member%* of two arguments  %3x%* and %3y%*.
%3x%* is to be an individual; %3y%* is to be a sequence;
%3member%* is to return
%et%* just in the case that %3x%* is  an element of the sequence %3y%*.
What does this specification tell us?
The predicate is partial. The recursion should be on the structure of %3y%*;
and termination (with value %ef%*) should occur if %3y%* is the empty sequence. 
If %3y%* is not
empty then it has a first element (call it %3z%*); compare %3z%* with %3x%*.
If these elements are identical then  %3member%* should return %et%*; otherwise
see if %3x%* occurs in the remainder of the sequence %3y%*.
.PT24
.GROUP
.FP
Notes:
.NL
%21.%*##We cannot use %3eq%* directly to check equality since, though %3x%* is an individual,
there is no
reason  that the elements of %3y%* need be.
We will introduce a subsidiary predicate %3same%1 to  assure that %3eq%1
is applied only to arguments of the correct type.
.NL
%22.%*##Recall that we can get the first element of a sequence with 
%3first%*,
and the rest of a sequence with %3rest%*.
.PT24
.APART
.GROUP;
.FP
So here's %3member%*:
.BEGIN TABIT2(16,32);SELECT 3;GROUP;turn on "←";
.BOXA
\member[x;y] <=\[null[y] → %ef%*;
\\ same[first[y];x] → %et%*;
\\ %et%* → member[x;rest[y]]]
.PT18
%1where:←%3same[u;v] <= [isindiv[u] → eq[u;v]; %et%3 → %ef%3]
.END
.BOXB
.APART
.GROUP;
Next  is an arithmetic example to calculate the 
number of elements in a sequence.
.boxa
.P118:
.BEGIN CENTERIT;SELECT 3;
←length[n] <= [null[n] → 0; %et%* → plus[1;length[rest[n]]]]
.END
.APART
.SS(Lists: Representations of Sequences,lists)
.FP
We can now write LISP-like functions describing
operations on sequences; the algorithms are clean and understandable.
However, if we wish to run these programs in a LISP environment, then
we have  to represent  the data structures and the
algorithms in terms understandable to LISP⊗↓If we wish LISP to
run on a conventional machine we have to represent
LISP's data structures and algorithms in a manner understandable
to that  hardware. This task is the subject of later chapters
in the book.←. This is the problem of representation. Granted, we
could have overcome the problem by  representing sequences directly
as LISP S-expressions and could have written functions in LISP which
used %3car-cdr%*-chains to directly manipulate the representations.
However, the resulting programs would be much more difficult 
to read and debug and understand.
More important, the programs 
would be  explicitly tied to a specific representation
of the abstract data structure. At some later date it 
might be desired to
change the representation; then many programs would have to be rewritten.
We will illustrate these difficulties soon.
In {yonss(P41)} we develop a complex algorithm for
differentiation on a class of polynomials, moving from an unclear
and highly representation-dependent formulation, to a clear, concise,
representation-independent algorithm. 

Obviously we will always have to supply a representational bridge between
the abstract data structures and algorithms, and their concrete counterparts.
One aspect of this study of data structures is to understand what is
required to build this bridge and how best to represent these requirements
in a programming language.

The first decision to be made is how to represent the abstract data structure;
how  should we represent sequences as S-expressions? How should we
choose representations in general? Usually there is not just one "best" 
representation. Some obvious considerations involve the difficulty of
implementing the primitive operations (constructors, selectors,
recognizers, and predicates) on the abstract data structure. Also we must
keep in mind the kinds of algorithms which we wish to write;
computation takes time, and since this is computer science we should
give consideration to efficiency.

.GROUP
A reasonable choice for a representation of sequences as S-expressions
is the following:

.BEGIN CENTERIT;
.boxa
←%9r%f(%1<indiv>%f)%1 = %1<atom>%1
.pt2
and for %9α%41%1,#...,#%9α%4n%1 in %d<seq elem>%*:
.END
.BEGIN SELECT g;NOFILL;PREFACE 0 MILLS;GROUP;
.TURN OFF "%","#";
.TURN ON "?" FOR "\"
.TURN ON "∞" FOR "%";
.KRK
.TABS 10,39;
?      ∞9r∞f(∞2 (∞9α∞41∞1, ..., ∞9α∞4n∞2) ∞f)∞1 = ∞G?         /\
?                     ?        /  \
?                     ?   ∞9r∞f(∞2 ∞9α∞41∞2 ∞f)∞g \
?                     ?             \
?                     ?              \
?                     ?              /\
?                     ?             /  \
?                     ?        ∞9r∞f(∞2 ∞9α∞42∞2 ∞f)∞g  
?                     ?                 ...
?                     ?                   \
?                     ?                   /\
?                     ?                  /  \ 
?                     ?                 /    \ 
?                     ?                /     ∞3NIL∞*
?                     ?           ∞9r∞f(∞2 ∞9α∞4n∞2 ∞f) 
.END
.BOXB
.APART

.BEGIN TURN ON "#";
.FP
The right-hand branch in this LISP-tree representation of a sequence
will always point to the rest of the sequence or will be the atom %3NIL%*.
Notice that the description of the %9r%*-mapping is recursive. Thus for example:

.GROUP;
.BEGIN SELECT g;NOFILL;PREFACE 0 MILLS;GROUP;
.TURN OFF "%","#";
.TURN ON "?" FOR "\"
.TURN ON "∞" FOR "%";
.TABS 15,46;
.KRK
.BOXA
?    ∞9r∞f(∞2 ((A,B,C),(D)) ∞f)∞1 = ∞G?          /\
?                     ?         /  \
? 		      ?        /    \ 
?                     ?  ∞9r∞f(∞2 (A,B,C) ∞f)∞g \
?                     ?               \
?                     ?                \
?		      ?                /\
?	 	      ?               /  \
?		      ?              /   ∞3NIL∞*
?                     ?         ∞9r∞f(∞2 (D) ∞f)∞g
.BOXB
.END
.FP
which will finally expand to %3((A . (B . (C . NIL))) . ((D . NIL) . NIL))%* 
since %9r%f(%2#(A,B,C)#%f)%1 is %3(A#.#(B#.#(C#.#NIL)))%1 and
%9r%f(%2#(D)#%f)%1 is %3(D#.#NIL)%*.
.APART

For convenience sake we will carry over the sequence notation --#%2(A,#B,#C)%*#--
to that for the representation in LISP --#%3(A,#B,#C)%*#--⊗↓
%1Be aware that
%3A%* is an atom and %2A%* is a sequence element; they are %6not%1 the same
data structure.←
thinking of %3(A,#B,#C)%* as an abbreviation for %3(A#.#(B#.#(C#.#NIL)))%*.
.END

Next,  what about a representation for the empty sequence? Looking at the
representation of a non-empty sequence it appears natural to take ⊗→%3NIL%*↔← as
%9r%f(%2(#)%f)%1 since after you have removed all the elements from the sequence
%3NIL%* is all that is left in the representation.
To be 
consistent  then:
.BEGIN CENTERIT;
.BOXA
←%9r%f(%2#(#)#%f)%1 = %3NIL%*.
.BOXB
.END
This gives us a complete specification of the %9r%*-mapping for the domain;
we have represented the abstract domain of sequences in a subset of the
domain of Symbolic Expressions. 
The S-expr representation of a sequence is called a %2list%*; and we
will refer to the abbreviation, 
.BEGIN CENTERIT;GROUP;
.BOXA
←%3(%9α%41%3,#...,#%9α%4n%3)%1   for   %3(%9α%41%3#.#(%9α%42%3#.##...#(%9α%4n%3#.#NIL)#...))%1    as %2⊗→list-notation↔←%*. 
.BOXB
.END
Sequences are the abstract data structure; lists are their representation.
Since the atom %3NIL%* takes on special significance in list-notation
it is endowed with the special name %2⊗→list terminator↔←%*.
.GROUP
And
a notational point:  in graphical interpretation of list-notation 
it is often convenient to write:

.BEGIN SELECT b;NOFILL;PREFACE 0 MILLS;GROUP;
.TURN OFF "%","#";
.TURN ON "∞" FOR "%";
.turn on "?" FOR "\"
.KRK
.TABS  20,48;
?⊂αααπααααα⊃         ? ⊂αααπαα⊃
?~   ~ NIL ~    ∞1as∞* ? ~   ~≤'~
?%ααα∀ααααα$         ? %ααα∀αα$

.END
.APART
%1
.GROUP
For example %3(A, (B, C), D)%* is:
.BEGIN SELECT b;NOFILL;PREFACE 0 MILLS;GROUP;
.KRK
.TURN OFF "%","#";
.TURN ON "∞" FOR "%";

		⊂αααπααα⊃  ⊂αααπααα⊃  ⊂αααπαα⊃
		~ A ~ #αβα→~ # ~ #αβα→~ D ~≤'~
		%ααα∀ααα$  %αβα∀ααα$  %ααα∀αα$
			     ~
			     ~   ⊂αααπααα⊃  ⊂αααπαα⊃
			     %αα→~ B ~ #αβα→~ C ~≤'~
				 %ααα∀ααα$  %ααα∀αα$

.END
.APART
or, in "dotted-pair" notation: %3 (A . ((B . (C . NIL)) . (D . NIL)))%1.
Finally, in list-notation the commas can be replaced by spaces⊗↓This convention
is one of the few instances of a "good" bug. The early LISP papers required
full use of commas, but due to a programming error in the LISP output routine,
lists were printed without commas. It looked so much better that the bug
became institutionalized.←
.BEGIN CENTERIT;
.PT18
%1←e.g. %3(A, (B, C), D) = (A (B C) D) 
.PT2
%1but beware: the "dots" in dot-notation are %6never%* optional!
.PT18
←%1that is   %3(A . (B . C)) %9≠%* (A (B C))
.PT18
.END

At this point  we have an intuitive understanding
of what we mean by "sequence"; we have described selectors,  constructors,
and  recognizers, albeit at an abstract level, for manipulating
sequences,  and we have  represented our notion of sequences
as a subset of the S-expressions called lists.
The final step is to represent our
sequence-manipulators as certain LISP functions.
Let %3first%4r%1 be a LISP function which will represent the sequence 
operation %3first%*⊗↓Indeed, once the %9r%*-mapping is defined
on the %6domain%* it is induced on the %6operations%*.←.
Then for example we might expect:

.BEGIN CENTERIT SELECT 3; TURN ON "#";
.BOXA
←%3first%4r%*[(A, B, C)] = %9r%f(%3 first[%2(A, B, C)%3] %f)%3 = A%1.
.BOXB
.BEGIN FILL;SELECT 1;
The problem is that this line is not quite right.
LISP functions  expect their inputs to be S-expressions
but %3(A,#B,#C)%* is %6not%* an S-expression.
To be correct we %6should%* have written:
.END
.BOXA
←%3first%4r%*[(A .(B . (C . NIL)))] = A%*
.BOXB
.END
It might be argued that %3(A, B, C)%* is just a convenient abbreviation
for  %3(A#.#(B#.#(C#.#NIL)))%*, but even so, if we wish the
machine to  use the abbreviation  we must be able to express that translation scheme
to the machine.
We must therefore examine the
implications of the notation. 
Clearly it is easier to read and write in list notation and,
as long as we perform only list-operations on lists, there is 
no reason to look at the underlying dotted-pair representation⊗↓Indeed,
a strong case can be made for %6never%* allowing any operations on lists
%6except%1 list operations! See the discussion of type-faults on {yon(P131)}
and {yon(P132)}.←.
However, we must keep in mind that list operations are carried out on the
machine using the dotted-pair representation. 
%6We%* might carry out the "list-to-dotted-pair"
 transformations implicitly, but a machine which evaluates LISP
expressions will have to have an explict transformation mechanism.
So a necessary part of our representation of
sequences is the specification of transformations between the
abstract data structure notation and the notation of the underlying
representation.
.BEGIN TURN ON "←";
We can give representations for the sequence operations.
We should continue to write
the subscript %4r%* on the LISP representation of a sequence operation, like
%3seq%*  being represented by %3seq%4r%1. 
In most circumstances the distinction between
abstraction and representation will be clear,
so we will usually omit the subscript.
The construction
of a sequence from an arbitrary number of elements 
will be represented by a LISP function
%3seq%4r%1. We will use %3list%* interchangeably with %3seq%4r%1.
.BEGIN CENTERIT;
.BOXA
←%9r%f(%3 seq %f)%* = list
.BOXB
.END

.group
⊗→%3list↔←%3[%9α%41%3; %9α%42%3; ... ;%9α%4n%3]%1 generates 
a list consisting of the 
%9α%4i%1 arguments. That is, for n%9≥%11,
%3list%1 
is the appropriately nested composition of %3cons%*es:

←%3cons[%9α%41%3;cons[%9α%42%3; ... cons[%9α%4n%3;NIL]] ...] %1, and for n#=#0, %3list[ ] = ( )%1.

.BEGIN GROUP;NOFILL;
Examples:
.select 3;
.EQ
list[A;B] = (A B)
.EQ1(29);
\list[A;B;C] = (A B C)
\list[A;list[B;C]] = list[A;(B C)] = (A (B C))
\list[NIL] = (NIL)
.PT18;
.END
.END
.apart
.FP
Notice that %3list%* is %6not%* strictly a LISP function;
it %6does%* evaluate its arguments,
but it can take an arbitrary number of them. On {yon(P111)} we
required that LISP functions be of fixed arity.
For the moment, %3list%* is simply a notational abbreviation for  nested 
applications of %3cons%*.
The representation of the selector functions should be apparent from the
graphical representation. 
We leave it as an exercise for the reader to specify representations 
for these functions; however, here are a few of the other representations:

.GROUP
.EQ
%9r%f(%3 isindiv %f)%* = atom  
.EQ1(22);
\%9r%f(%3 isseq %f)%* = isstrictlist%1  where:
.PT18;
.END
.BEGIN SELECT 3;TABIT2(12,31);TURN ON "←";
.P185:
.BOXA
\isstrictlist[x] <=\[atom[x] → [eq[x; NIL] → %et%3; %et%3 → %ef%3];
\\ islistelement[car[x]] → isstrictlist[cdr[x]];
\\ %et%3 → %ef%3]
.PT18;
%1where:%3←islistelement[x] <= [atom[x] → %et%3;   %et%3 → isstrictlist[x]]
.END
.BOXB
.APART
.GROUP;
.FP
The predicate %3atom%1 does not quite characterize %3isindiv%1.
We have been assuming that:


.BEGIN CENTERIT;
.BOXA
←%9r%F(%3f[t%41%3; ...; t%4n%3]%f)%1 = %9r%F(%3f%f)%3[%9r%F(%3t%41%3%f)%3;%9r%F(%3t%42%3%f)%3; ...; %9r%F(%3t%4n%3%f)%3]
.BOXB
%1but%1 ←%9r%f(%3isindiv[( )]%f)%1 %9≠%1 %9r%f(%3isindiv%f)%3[%9r%f(%3( )%f)%3]%1
.END
.BOXB
.APART
.FP
Some descriptions of LISP use this strict definition of lists,
so that elements of a list are either atomic or are lists themselves.
In practice it is often convenient to allow 
elements of a list to be arbitrary S-expressions. This more liberal
interpretation of lists is expressed by the following recognizer:
.BEGIN CENTERIT;
.BOXA
←%3islist[x] <= [atom[x] →[eq[x;NIL]→%et%*;%et%*→%ef%*]; %et%*→islist[cdr[x]] ]
.BOXB
.END
.FP
Therefore %3(A,#(A#.#B),#C)%* is a list of three elements.
But beware: %2(A,#(A#.#B),#C)%* is %6not%* a sequence,
and neither is  %3(A,#(A#.#B),#C)%1.


.END
.SELECT 1;
.GROUP;
Since lists may have dotted pairs as elements, it is natural to
extend %3list%1 to handle such cases:
.BEGIN CENTERIT;SELECT 3;
.BOXA
←list[cons[A;B];car[(A . B)]] = ((A . B) A)
.BOXB
.END
.APART
.GROUP;
.P116:
To summarize the accomplishments of this section, we have  in
effect added a %6new%* data structure to the repertoire of LISP.
The addition process included:

.BEGIN INDENT 0,10,10;

%21.  The abstract operations.%* We give constructors, selectors, and predicates for
the recognition of instances of the data structure.

%22.  The underlying representation.%* We must show how the new data
structure can be represented in terms of existing data structures.

%23.  Abstract operations as concrete operations.%* We must write LISP
functions which faithfully mirror the intended meaning of the abstract operations
when interpreted in the underlying representation.

%24.  The input/output transformations.%* We should give conventions
for transforming to and from the internal representation.
.BOXB
.END
.APART
There is another view of the representability of  data structures
(⊗↑[Mor#74]↑). We use  %2transfer functions%1 which are
mappings between the abstract structure and its representation.
We need two transfer functions;
a write-function, %2W%*, to map the representations into the abstract objects;
and a read-function, %2R%*, to map the abstract objects to their representations.

Consider the problem of representing sequences. We want %2R%* to map from
elements of %d<seq elem>%* to %d<sexpr>%* (see {yon(P114)} and {yon(P115)}); and
we want %2W%* to map from %d<sexpr>%* to %d<seq elem>%*.
Before we give such %2R%* and %2W%*, let's see what they will do for us.
We could define %3first%4r%1 such that:
.BEGIN CENTERIT;
.BOXA
←%3first%4r%*[x] = %2W%*[car[%2R%*[x]]]
.BOXB
.END
.FP
What the equation says is that given a 
sequence %3x%*, we can map it to the S-expression representation using %2R%*;
the result of this map is an S-expr and therefore suitable fare for %3car%*;
the result of the %3car%* operation is then mapped back into
the set of sequence elements  by %2W%*.
The other operations for manipulating sequences can be described similarly.
With this introduction, here are  appropriate transfer functions:

.BEGIN TABIT1(10);SELECT 3;
.GROUP
.BOXA
%2W%*[e] <=\[isnil[e] → mknull[];
\ atom[e] → mkindiv[e];
\ %et%* → concat[%2W%*[car[e]];%2W%*[cdr[e]]] ]
.END
.BOXB
.BEGIN TABIT1(9);SELECT 3;
.GROUP
.BOXA
%2R%*[l] <=\[null[l] → NIL;
\ isindiv[l] → atomize[l];
\ %et%* → cons[%2R%*[first[l]];%2R%*[rest[l]]] ]
.BOXB
.END
.FP
We have seen all of the functions and predicates involved in %2R%* and %2W%*
except %3atomize%*, %3mknull%1 and %3mkindiv%*. In terms of our current
representation of sequences, these three functions are essentially 
the identity function, %3i[x]#<=#x%1. 
However that is true %6only%1 because of the particular
representations that we  picked; the functions need not be so simple.
A more careful  inspection would show that %3mkindiv%* expects as input an atomic
S-expression and outputs a sequence individual; %3atomize%* acts
conversely. If the representations of the atomic S-expressions were different
from the representations of sequence individuals, then we would have some
work to do.


We review what has transpired since it is a model of what is to come.
We developed a new  abstract data structure called sequences; discussed
notational conventions for writing sequences; described
operations and pertinent control structures for writing algorithms;
and finally  showed that
it was possible to represent sequences in the previously developed
domain of S-exprs. If we had a machine which could execute
S-expr algorithms we could encapsulate that machine within the %9r%*-mapping
such that we could write in sequence-notation and have it translated internally to
S-expr form; we could write sequence-algorithms and have them execute correctly
using the %9r%*-maps of the sequence primitives; and finally it would
produce sequence-output rather than the internal S-expr form. For all intents
and purposes our augmented LISP  machine understands sequences.
Indeed, this is the way most LISP implementations are organized; input 
may either be in S-expr form or list-notation; internally all data structures
are stored as S-exprs; all algorithms operate on the S-expr form; and finally,
 any S-exprs which can be interpreted as lists are output in list-notation.

We will approach the other abstract data structure problems in a similar manner,
first developing the data structures independent of their representation, and
later showing how to  represent this new domain in terms of some previously 
understood domain. We will see in {yonss(P105)} that much of the
mapping from input through output can be specified in a natural style
and LISP can automatically generate the necessary input and output
programs.

.REQUIRE "PROB4.PUB" SOURCE_FILE;
.SS(A Respite,,P290:)
.SELECT 1;

.EP;
"...I think that one of the chief difficulties is that
the general standard of programming is extremely low.
 ...I think that I would like to suggest again that the general
standards of programming and the way  in which people are
taught to program is abominable. They are over and over again
taught to make puns; to do shifts instead of multiplying
when they mean multiplying; to multiply when they mean shifts;
to confuse bit patterns and numbers and generally to say one thing
when they actually mean something quite different. Now this
is the standard  way of writing a program and they take 
great pleasure in doing so-"Isn't it wonderful? It saves a quarter of
 a microsecond  somewhere every month". Now I think we will not 
get a proper standard of programming ... until we can have some
proper professional standards about how to write programs;
and this has to be done by teaching people right  at the beginning
how to write programs properly ..."

.PT24;
.BEGIN TURN ON "→";
→C. Strachey,  %3Conference on Software Engineering, 1968%1#######
.END
.PT24;PT24;PT2;

.BEGIN TURN ON "←";
.FP
This section summarizes and reflects on the  material of
this chapter. First a reiteration of a previous admonition: though most of
this material may seem quite straightforward, the next chapter will begin
to show you that things are not all that trivial.  LISP is quite powerful.
The preceding material %6is%* basic and the sooner it becomes second nature
to you the better.  

A second admonition: besides learning about the basic constructs of the language,
the previous material should begin to convince you of the necessity for
precise specification of programming languages. 
In particular we have seen that the process of evaluation of expressions
must be spelled out quite carefully. Different evaluation schemes lead to
quite different effects. Since evaluation %6is%* the business of programming
languages  we'd better do all we can to make a precise specification.

And a final warning: 
a major point of this whole book is to instill a respect for abstraction
as a tool for controlling complexity in programming, and as a means of
writing implementation  independent programs. As we begin
writing more complex algorithms, the power of abstraction will become more
apparent, but the lessons we learned in representing
sequences contain the essential ideas of abstraction and representation.

We have now seen two examples of abstract data structures. First, we studied
S-expressions without any consideration for their implementation;
they were abstract objects of sufficient interest in their own right.
We then introduced  the operations on the
data structures: %3car, cdr, cons, eq%* and %3atom%*. 
Finally the %2⊗→control structures↔←%*,
conditional expression and recursion, were given. 
Control structures  are used to direct the flow
of the algorithm as it executes.
These three components, data, operations, and control, are the
main ingredients of any programming language.
Most languages have an apparently richer class of control devices;
"while"-statements and "DO"-loops are examples. Later we will show how
to introduce such constructs into LISP.
Most control structures
are explicit language constructs like the conditional expression, 
whereas recursion is typically implicit⊗↓However
some languages do require some kind of declaration to the effect that a
procedure is recursive.←. The interaction between recursion and the 
procedure-calling mechanism gives LISP a  powerful control structure.

As we introduce each new abstract data structure we add new operations tailored
to its needs. When we introduced sequences we 
also introduced %3first, rest, null,#...%*,etc.
We did not add any new control structure,
though
a simpler control structure which operated on sequences, selecting elements
and performing operations on those elements,
might be useful.
There is a
natural relationship between data structure and control structure;
sometimes we can exploit it to good measure.
When we consider abstract data structures in future chapters we will again 
see the three components: data, operations, and control. 

The new feature which we considered in discussing sequences was the problem
of representation. We showed how to represent sequences in terms of
S-expressions. We will continue this pyramiding of data structures in the future;
we will consider our work done as soon as we have a representation
of our new data structure in terms of an existing one. Finally
 we will exhibit a representation
of the underlying layer of S-expressions. Later we will discuss
different representations of data structures, independent of their possible
S-expression representation;  there are data
structures  which are not best represented as S-expressions.
A further consideration appears because of the representation issue;
even though we have represented a particular data structure as a 
complex S-expression we should not operate  on that representation
with S-expression functions. We should refrain from using %3car%* and %3cdr%*  on 
lists even though  the representation is well-known.
In our representation of lists we could find the n%8th%* 
element in a list  by using %3cad%8n-1%*r%1. And we know
that %3cdr%* represents the %3rest%* of the list.
Though our representation of sequences is such that %3first%*, %3rest%*
and %3concat%*
are identical to %3car%*, %3cdr%*, and %3cons%* respectively, we should
use the names %3first%*, %3rest%*, and %3concat%* 
to make it clear that we are operating on lists.
These representation-dependent coding
tricks⊗↓called "puns" by C. Strachey← are dangerous. They are
really type faults as discussed on {yon(P131)} and {yon(P132)}.

For a more practical  benefit, consider the problem of program modification.
We might wish to change the representation of  a data structure. If the programming
has been done in terms of abstract operations on abstract data structures
then only those functions which relate the abstraction
to the representation need be changed. If we had used the representation
throughout the program, then every use of the representation must be changed.
While we are discussing some of the more practical implications of our work
we should discuss how %9B%1  should  be understood.
As things currently stand, the appearance of %9B%1  in any application
of strict functions will immediately cause the termination of the computation.
No information other than the fact that %9B%1 did appear results from such
an occurrence. If we thought of the evaluation of %9B%1 as resulting in
a divergent computation, then no information at all would be forthcoming.
In reality, a LISP implementation can handle many computations which involve
%9B%1. The computation might
be terminated and an error  printed; in an interactive implementation,
the user might be given an opportunity to correct the  error and 
have the computation
continue; and alas, some implementations just continue computation with
some arbitrary piece of information produced by an excursion into
the subsconscious of LISP. 
Divergent computations cannot be detected in such a clear manner and
implementations differ in their handling of this interpretation of %9B%1.
We will have more to say about
the implementation of %9B%1 in {yonss(P168)}.


Later, we will motivate the more traditional studies of data structures
by considering the implementations of LISP-related languages.
But the path to those studies is at least as important. On the way
we will show that we can exploit abstraction as a means for
giving a clear specification of evaluation of LISP expressions, and
the  representational techniques we will use will involve applications
of abstract data structures. A more tangible benefit  should be
an increased awareness of the structure and behavior of programming languages,
and the beginnings of a better style of programming.

.P147:
Another part of our investigation should be to answer the question
"What is a data structure?".
As we mentioned at the beginning of {yonss(P100)}  there is a different 
characterization of sequences which will give a different interpretation
of data structures. The standard  mathematical definition of
a sequence is as a function from the integers to a particular domain.
.GROUP;
Thus a finite sequence %ds%* might be given as:
.BEGIN TURN OFF "{","}";CENTERIT;
.BOXA
←%ds%1 = %*{<1, s%41%*>, <2, s%42%*>, ...<n, s%4n%*>}
.BOXB
.END
.APART
.FP
To select components of %ds%*, we  use ordinary function application:
%ds(i)%1#=#%*s%4i%1. Indeed, if you have programmed in a language which 
has array constructs, you will recognize "application" as 
the style of notation used: A[3]#selected the 3%8rd%1 component for the 
array#A.
.GROUP;
However this is quite different from what we did in the section on sequences.
For example, if %2(A,#B,#C)%* is a sequence, %ds%*, then in the new interpretation
we should write:
.BEGIN TURN OFF "{","}";CENTERIT;
.BOXA
←%ds%1 = %*{<1, %2A%*>, <2, %2B%*>,<3, %2C%*>}
.BOXB
.END
.APART
.FP
Thus %ds(2)%1 is %2B%*, etc. What has happened is that what was previously
considered to be a data structure has become a function, and the selector
functions on the data structure have now become static indices on the
function.
Or to make things more transparent:
.BEGIN TURN OFF "{","}";CENTERIT;
.BOXA
←%ds%1 = %*{<%3first%*, %2A%*>, <%3second%*, %2B%*>,<%3third%*, %2C%*>} 
.BOXB
.END
.FP
Then we  would write %ds(%3first%*)%1 rather than %3first%d(s)%1⊗↓G. Steele 
(⊗↑[Ste#pc]↑) reports that PPL 
(Polymorphic Programming Language) at Harvard lets you do this: %3car[s]%1 and
%3s[car]%1 both work.←.
This idea can easily be applied to S-exprs and their functions. 
In graphical terms
we are representing the structures such that the arcs of the graph
are labeled with the selector indices. With L-trees 
the labeling was implicit: left-branch was %3car%*; right-branch was %3cdr%*.
With explicit labels on the branches, the trees need not  be ordered.
Several languages implement such unordered trees; they are called
%3structure%*s in Algol#68 and EL1, and called %3record%*s in Pascal.
Several formalisms exploit this view of data structures; in 
particular the Vienna Definition Language#(⊗↑[Weg#72]↑), 
which is a direct descendant of LISP,
represents its data in such a manner.

What then is a  data structure? It depends on how you look at it. For our
immediate purposes we will try to remain intuitive and informal.
We will try to characterize an abstract data structure as a domain and
a collection of associated operations and  control structures. The operations and
control mechanisms should allow us to describe algorithms in a natural manner
but should, if at all possible, remain representation independent.

A few tricks were embedded in the problem sets.
Recall problem %2h%* on {yon(P11)}. The composition %3atom[cons[ ...]]%*
will always evaluate to %ef%* ⊗↓%1If it has a value at all!
If the computation of the arguments to the %3cons%* does not
terminate or gives %9B%1 then we won't
get %ef%*.←
since the result of %3cons%1 is always
non-atomic.
In %2j%*, we used atoms with  the same
letter strings as predicate names, %3ATOM%* and %3EQ%*. 
####%3ATOM%* and %3EQ%*
are perfectly good atoms, and are %6not%* to be confused with the LISP predicates.
Problem#%2p%*  shows that conditional expressions may
appear within a functional composition.

.BEGIN TURN ON "#";
Notice that %3twist%* in problem 2 is total whereas %3findem%* is partial ≤~(JgMS9IKZJ(ASfAACeiS¬XAgS9GJ@JMrJTA5kghA	JACi=[SF\↓¬←iP↓Mk]GQS←]f↓EkSY⊂@~∃]∃nAie∃Kft@∀gioSMiKZJ(AeKm∃egKf↓YKMh4AC]H↓eSOQP[EeC9GQKf↓eKGkIgSmK1rv~∀∀gMS]⊃KZJT↓EkSY⊃fABAQeKJA]SiPAQQJAg¬[JAEIC]GQ%]NAgQekGiUeJACL@Jgp∀TX~∃	khAi!JAiKI[S]C0A]←I∃fAG←9iCS\Jg(J(AChAQQJAa=S]if↓oQKe∀AiQJ↓Ci←ZJgrJ(~∃CaAKCef↓S\Ai!JA←e%OS]C0AieK∀XAC]⊂@Jg≥%_JTA=iQKe]SgJ\4∀] dPt~∀]∃≥λ~∀4∃¬JA
YKCd↓←\Ai!JAIS→MKeK9GJAE∃ioKK8AiQJ↓eKae∃gK]i¬iS←\↓←LAi!JAK[AirAY%ght@∀g≥∪_∀TXAC9H@~∃QQJAY%ghAG=]gSgQS]NA=L@Jg9∪_JTh@JfQ9∪_RJ(vA]←QJAiQ¬h@Jf!≥∪_R∀TASf~∃C\↓CEEe∃mSCi%←\AM=d@Jf!≥∪_@8A≥∪_$JTXA]QSGP↓GKei¬S]Yr↓SfA]=h@Jg9∪_JT8~∃→SMh[]←QCiS←8ASf@↓C\AC	EeKm%CiS←8AC]H↓GC\A¬YoCsLAEJAQeC]g1CiKH↓ECGV4∃S]i<ABA&5Kqad0AEkh↓]←hA∃mKer↓&[KqAdASf↓iQJAIKaeKMK]iCQS←\A=LABA1Sgh\4∀~∃)!JAISMiS]GQS←\A	KioK∃\@Jg
←]GCPJbAC9H@Jg1SghJDASfAM←[Ki%[KfA
←]MkMS]Nt4∀]!(Hh~∃>∀gG←]
Ci6Jd∧Jhb∀fv@P∀r∧JhHJfX@8\\JrλJi\JLS:JbFFASL@FFF∀fPJrλJhbJLX@JrλJhdJLX@\\8@Jr∧∀i\Jf$\~∀]A(bp~)>JgY%gi6Jd∧Jhb∀fvPJd∧Jhd∀fX@\8\@JrλJi\JLS:JbFFASLFFF@∀fPJrλJhbJL@PJrλJhdJL@\\\Jr∧JQ\JfR$Jb\~(]!(dP~∀]
@~∃'↑JgG←9GChJ(AoSY0ACIH↓BA]K\AKYK5K]hAQ↑AiQ∀AMe←9hA←L↓C\AKaSgiS9NAYSMhX@~)oQKe∃Cf@JMYSgh∀T~∃o%YXAGIKCiJ↓BA]K\AYSgPAoQ←MJAKY∃[K]iLAoSY0AEJAQQJAm¬YkKf↓←LAi!JACe≥k[K]Qf~∃i<@JgY%ghJT8~∀~∀9≥λ~(~∀